algorithm - Maximum product prefix string -

the following demo question coding interview site called codility:

a prefix of string s leading contiguous part of s. example, "c" , "cod" prefixes of string "codility". simplicity, require prefixes non-empty.

the product of prefix p of string s number of occurrences of p multiplied length of p. more precisely, if prefix p consists of k characters , p occurs t times in s, product equals k * t.

for example, s = "abababa" has following prefixes:

• "a", product equals 1 * 4 = 4,
• "ab", product equals 2 * 3 = 6,
• "aba", product equals 3 * 3 = 9,
• "abab", product equals 4 * 2 = 8,
• "ababa", product equals 5 * 2 = 10,
• "ababab", product equals 6 * 1 = 6,
• "abababa", product equals 7 * 1 = 7.

the longest prefix identical original string. goal choose such prefix maximizes value of product. in above example maximal product 10.

below poor solution in java requiring o(n^2) time. apparently possible in o(n). thinking kadanes algorithm. can't think of way can encode information @ each step lets me find running max. can 1 think of o(n) algorithm this?

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;     } } 

here's o(n log n) version based on suffix arrays. there o(n) construction algorithms suffix arrays, don't have patience code them.

example output (this output isn't o(n), it's show can indeed compute scores):

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

basically have reverse string, , compute suffix array (sa) , longest common prefix (lcp).

then have traverse sa array backwards looking lcps match entire suffix (prefix in original string). if there's match, increment counter, otherwise reset 1. each suffix (prefix) receive "score" (scr) corresponds number of times appears in original string.

#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);              (int = 0; < n; i++)                 c[i + k < n ? ra[i + k] : 0]++;      int sum = 0;     (int = 0; < max(256, n); i++) {                              int t = c[i];          c[i] = sum;          sum += t;     }      (int = 0; < 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();      (int = 0; < n; i++)          ra[i] = s[i] - 1;                    (int = 0; < n; i++)          sa[i] = i;      (int k = 1; k < n; k *= 2) {              suffix_sort(n, k);         suffix_sort(n, 0);          int r = tempra[sa[0]] = 0;         (int = 1; < 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;              (int = 1; < n; i++)           phi[sa[i]] = sa[i-1];        int l = 0;     (int = 0; < 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);                           }      (int = 1; < n; i++)                          lcp[i] = plcp[sa[i]]; }  void score(string &s) {     scr[s.size()-1] = 1;      int sum = 1;     (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;     } } 

most of code (specially suffix array , lcp implementations) have been using years in contests. version in special adapted this 1 wrote years ago.