Das Folgende ist eine Demo-Frage von einer Coding-Interview-Site namens codility:

Ein Präfix einer Zeichenfolge S ist ein beliebiger führender zusammenhängender Teil von S. Beispielsweise sind "c" und "cod" Präfixe der Zeichenfolge "codility". Der Einfachheit halber müssen Präfixe nicht leer sein.

Das Produkt des Präfixes P der Zeichenfolge S ist die Anzahl der Vorkommen von P multipliziert mit der Länge von P. Wenn das Präfix P aus K Zeichen besteht und P genau T-mal in S vorkommt, ist das Produkt gleich K * T.

Zum Beispiel hat S = "abababa" die folgenden Präfixe:

"a", dessen Produkt 1 * 4 = 4 ist, "ab", dessen Produkt 2 * 3 = 6 ist, "aba", dessen Produkt 3 * 3 = 9 ist, "abab", dessen Produkt 4 * 2 = 8 ist, "ababa", dessen Produkt 5 * 2 = 10 ist, "ababab", dessen Produkt gleich 6 * 1 = 6 ist, "abababa", dessen Produkt gleich 7 * 1 = 7 ist.

Das längste Präfix ist identisch mit der ursprünglichen Zeichenfolge. Ziel ist es, ein Präfix zu wählen, das den Wert des Produkts maximiert. Im obigen Beispiel ist das maximale Produkt 10.

Below ist meine schlechte Lösung in Java, die O (N ^ 2) Zeit benötigt. Dies ist anscheinend in O (N) möglich. Ich dachte Kadanes Algorithmus. Aber ich kann mir nicht vorstellen, wie ich bei jedem Schritt einige Informationen codieren kann, mit denen ich das laufende Maximum ermitteln kann. Kann sich jemand einen O (N) -Algorithmus dafür vorstellen?

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