最大產品前綴字符串

Question

以下是從編碼採訪現場稱爲codility演示問題：

一個串S的前綴是S的任何前導連續一部分。例如，「c」和「鱈魚「是字符串」可信度「的前綴。爲了簡單起見，我們要求前綴非空。

字符串S的前綴P的乘積是P的出現次數乘以P的長度。更確切地說，如果前綴P由K個字符組成並且P在S中恰好出現T次，那麼乘積等於K * T.

例如，S = 「ABABABA」 具有以下前綴：

• 「一」，其乘積等於1 * 4 = 4，
• 「AB」，其乘積等於2 * 3 = 6,
• 「aba」，其乘積等於3 * 3 = 9,
• 「ABAB」，其乘積等於4 * 2 = 8，
• 「巴」，其乘積等於5×2 = 10，
• 「ABABAB」，其乘積等於6 * 1 = 6，
• 「abababa」，其產品等於7 * 1 = 7.

最長的前綴與原始字符串相同。目標是選擇這樣的前綴以最大化產品的價值。在上面的例子中，最大的產品是10.

以下是我在Java中需要O（N^2）時間的糟糕解決方案。 O（N）顯然可以做到這一點。我在想Kadanes算法。但我想不出任何可以在每個步驟中編碼一些信息的方法，這些信息可以讓我找到最大運行時間。任何人都可以爲此考慮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（n），但它只是表明我們確實可以計算所有分數）：

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