Максимального продукт префикс строка

Question

Ниже демонстрационный вопрос от кодирования интервью сайта под названием codility:

Префиксом из строки S является любой ведущей смежной части S. Например, «с» и «треск "являются префиксами строки" codility ". Для простоты мы требуем, чтобы префиксы были непустыми.

Произведение префикса P строки S представляет собой число вхождений P, умноженное на длину P. Точнее, если префикс P состоит из K символов, а P имеет ровно T раз в S, то произведение равно K * Т.

Например, S = "abababa" имеет следующие префиксы:

• "а", у которых произведение равно 1 * 4 = 4,
• "AB", продукт которого равен 2 * 3 = 6,
• «aba», продукт которого равен 3 * 3 = 9,
• "ABAB", продукт которого равен 4 * 2 = 8,
• "Абебу", продукт которого равен 5 * 2 = 10,
• "ABABAB", продукт которого равен 6 * 1 = 6,
• «Абабаба», продукт которого равен 7 * 1 = 7.

Самый длинный префикс идентичен исходной строке. Цель состоит в том, чтобы выбрать такой префикс, который максимизирует ценность продукта. В приведенном выше примере максимальный продукт равен 10.

Ниже мое слабое решение на Java требует O (N^2) времени. По-видимому, это возможно сделать в O (N). Я думал о алгоритме Каданеса. Но я не могу придумать, каким образом я могу кодировать некоторую информацию на каждом шаге, что позволяет мне найти макс. Может ли кто-нибудь подумать об алгоритме O (N) для этого?

import java.util.HashMap; 

class Solution { 
    public int solution(String S) { 
     int N = S.length(); 
     if(N<1 || N>300000){ 
      System.out.println("Invalid length"); 
      return(-1); 
     } 
     HashMap<String,Integer> prefixes = new HashMap<String,Integer>(); 
     for(int i=0; i<N; i++){ 
      String keystr = ""; 
      for(int j=i; j>=0; j--) { 
       keystr += S.charAt(j); 
       if(!prefixes.containsKey(keystr)) 
        prefixes.put(keystr,keystr.length()); 
       else{ 
        int newval = prefixes.get(keystr)+keystr.length(); 
        if(newval > 1000000000)return 1000000000; 
        prefixes.put(keystr,newval); 
       } 
      } 
     } 
     int maax1 = 0; 
     for(int val : prefixes.values()) 
      if(val>maax1) 
       maax1 = val; 
     return maax1; 
    } 
} 

Answer 1

Настоящая версия O (n log n) основана на массивах суффиксов. Есть алгоритмы построения O (n) для массивов суффикса, у меня просто нет терпения, чтобы их кодировать.

Пример вывода (этот вывод не O (п), но это только, чтобы показать, что мы действительно можем вычислить все баллы):

4*1 a 
3*3 aba 
2*5 ababa 
1*7 abababa 
3*2 ab 
2*4 abab 
1*6 ababab 

В основном вы должны обратить строку, и вычислить суффикс-массив (SA) и самый длинный общий префикс (LCP).

После этого вы перемещаете массив SA назад, ища LCP, которые соответствуют всему суффиксу (префикс в исходной строке). Если есть совпадение, увеличьте счетчик, в противном случае сбросьте его до 1. Каждый суффикс (префикс) получает «счет» (SCR), который соответствует количеству раз, которое оно появляется в исходной строке.

#include <iostream> 
#include <cstring> 
#include <string> 
#define MAX 10050 
using namespace std; 

int RA[MAX], tempRA[MAX]; 
int SA[MAX], tempSA[MAX]; 
int C[MAX];     
int Phi[MAX], PLCP[MAX], LCP[MAX]; 

int SCR[MAX]; 

void suffix_sort(int n, int k) { 
    memset(C, 0, sizeof C);   

    for (int i = 0; i < n; i++)   
     C[i + k < n ? RA[i + k] : 0]++; 

    int sum = 0; 
    for (int i = 0; i < max(256, n); i++) {      
     int t = C[i]; 
     C[i] = sum; 
     sum += t; 
    } 

    for (int i = 0; i < n; i++)   
     tempSA[C[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i]; 

    memcpy(SA, tempSA, n*sizeof(int)); 
} 

void suffix_array(string &s) {    
    int n = s.size(); 

    for (int i = 0; i < n; i++) 
     RA[i] = s[i] - 1;    

    for (int i = 0; i < n; i++) 
     SA[i] = i; 

    for (int k = 1; k < n; k *= 2) {  
     suffix_sort(n, k); 
     suffix_sort(n, 0); 

     int r = tempRA[SA[0]] = 0; 
     for (int i = 1; i < n; i++) { 
      int s1 = SA[i], s2 = SA[i-1]; 
      bool equal = true; 
      equal &= RA[s1] == RA[s2]; 
      equal &= RA[s1+k] == RA[s2+k]; 

      tempRA[SA[i]] = equal ? r : ++r;  
     } 

     memcpy(RA, tempRA, n*sizeof(int)); 
    } 
} 

void lcp(string &s) { 
    int n = s.size(); 

    Phi[SA[0]] = -1;   
    for (int i = 1; i < n; i++) 
     Phi[SA[i]] = SA[i-1]; 

    int L = 0; 
    for (int i = 0; i < n; i++) { 
     if (Phi[i] == -1) { 
      PLCP[i] = 0; 
      continue; 
     } 
     while (s[i + L] == s[Phi[i] + L]) 
      L++; 

     PLCP[i] = L; 
     L = max(L-1, 0);      
    } 

    for (int i = 1; i < n; i++)     
     LCP[i] = PLCP[SA[i]]; 
} 

void score(string &s) { 
    SCR[s.size()-1] = 1; 

    int sum = 1; 
    for (int i=s.size()-2; i>=0; i--) { 
     if (LCP[i+1] < s.size()-SA[i]-1) { 
      sum = 1; 
     } else { 
      sum++; 
     } 
     SCR[i] = sum; 
    } 
} 

int main() { 
    string s = "abababa"; 
    s = string(s.rbegin(), s.rend()) +"."; 

    suffix_array(s); 
    lcp(s); 
    score(s); 

    for(int i=0; i<s.size(); i++) { 
     string ns = s.substr(SA[i], s.size()-SA[i]-1); 
     ns = string(ns.rbegin(), ns.rend()); 
     cout << SCR[i] << "*" << ns.size() << " " << ns << endl; 
    } 
} 

Большой частью этого кода (специально массив суффиксов и реализации LCP) я использую в течение нескольких лет в конкурсах. Эта версия в специальном я адаптирована от this one I wrote some years ago.

Answer 2

public class Main { 
    public static void main(String[] args) { 
     String input = "abababa"; 
     String prefix; 
     int product; 
     int maxProduct = 0; 
     for (int i = 1; i <= input.length(); i++) { 
      prefix = input.substring(0, i); 
      String substr; 
      int occurs = 0; 
      for (int j = prefix.length(); j <= input.length(); j++) { 
       substr = input.substring(0, j); 
       if (substr.endsWith(prefix)) 
        occurs++; 
      } 
      product = occurs*prefix.length(); 
      System.out.println("product of " + prefix + " = " + 
       prefix.length() + " * " + occurs +" = " + product); 
      maxProduct = (product > maxProduct)?product:maxProduct; 
     } 
     System.out.println("maxProduct = " + maxProduct); 
    } 
}