最大产品前缀字符串

Question

以下是一个名为codility的编码访谈网站的演示问题:

字符串S的前缀是S的任何前导连续部分.例如,"c"和"cod"是字符串"codility"的前缀.为简单起见,我们要求前缀非空.

字符串S的前缀P的乘积是P的出现次数乘以P的长度.更准确地说,如果前缀P由K个字符组成并且P在S中恰好出现T次,那么乘积等于K*T.

例如,S ="abababa"具有以下前缀:

• "a",其产品等于1*4 = 4,
• "ab",其产品等于2*3 = 6,
• "aba",其产品等于3*3 = 9,
• "abab",其产品等于4*2 = 8,
• "ababa",其产品等于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)，该分数对应于它在原始字符串中出现的次数。

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

大部分代码（特别是后缀数组和 LCP 实现）我已经在比赛中使用了很多年。这个版本特别是我根据几年前写的这个版本改编的。