最大产品前缀字符串

Question

以下是来自名为 codility 的编码面试网站的演示问题：

A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty.

The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals K * T.

For example, S = "abababa" has the following prefixes:

"a", whose product equals 1 * 4 = 4,

"ab", whose product equals 2 * 3 = 6,

"aba", whose product equals 3 * 3 = 9,

"abab", whose product equals 4 * 2 = 8,

"ababa", whose product equals 5 * 2 = 10,

"ababab", whose product equals 6 * 1 = 6,

"abababa", whose product equals 7 * 1 = 7.

The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 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。每个后缀（前缀）都会收到一个 "score" (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);
    }
}

Answer 3

我为这个挑战工作了 4 天多，阅读了很多文档，我找到了 O(N) 的解决方案。

我得到了 81%，这个想法很简单，使用 window 幻灯片。

def 解决方案（s：字符串）：Int = {

var max = s.length  // length of the string 
var i, j = 1  // start with i=j=1 ( is the beginning of the slide and j the end of the slide )
val len = s.length // the length of the string 
val count = Array.ofDim[Int](len)  // to store intermediate results 

while (i < len - 1 || j < len) {
  if (i < len && s(0) != s(i)) {
    while (i < len && s(0) != s(i)) {  // if the begin of the slide is different from 
                                      // the first letter of the string skip it 
      i = i + 1
    }
  }
  j = i + 1
  var k = 1


  while (j < len && s(j).equals(s(k))) { // check for equality and update the array count 
    if (count(k) == 0) {
      count(k) = 1
    }
    count(k) = count(k) + 1
    max = math.max((k + 1) * count(k), max)
    k = k + 1
    j = j + 1
  }

  i = i + 1

}

max // return the max

}

最大产品前缀字符串

Maximum product prefix string

algorithm

performance

dynamic-programming

kadanes-algorithm