Наибольшая длина общего префикса из всех подстрок и строки

Question

Я нашел похожие вопросы на Stackru, но мой вопрос другой.

Учитывая строку s содержит строчные буквы alphabet, Я хочу найти длину Longest common Prefix всех подстрок.

Например

s = 'ababac'

Тогда подстроки выглядят следующим образом:

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

Теперь длина LCP из всех подстрок, как следует

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

Я использую символ за соответствием

    string commonPrefix(string s1, string s2) { 
        int minlen = minlength1(s1, s2); 
        char current; 
        int result = 0;
        for (int i=0; i<minlen; i++) { 
            current = s1[i]; 
            for (int j=1 ; j<n; j++) 
                if (s2[i] != current) 
                return result; 
            result++;
        } 

        return result; 
    }

Но все же, это O(n2). Я знаю, что все подстроки перекрывают друг друга, это может быть оптимизировано в дальнейшем. Кто-нибудь может помочь оптимизировать этот код?

Answer 1

Как упоминал Адитья, эту проблему можно решить с помощью Z-алгоритма. Подробное объяснение с реализацией можно найти здесь - https://www.hackerearth.com/practice/algorithms/string-algorithm/z-algorithm/tutorial/

Answer 2

Это похоже на Z-алгоритм сопоставления с образцом. За исключением первого случая, когда len(LCP(s(1, 6), s)) = len (s).

Нам нужно создать Z-массив. Для строки str[0..n-1] массив Z имеет ту же длину, что и строка. Элемент Z[i] массива Z хранит длину самой длинной подстроки, начиная с str[i], которая также является префиксом str[0..n-1]. Первая запись массива Z имеет меньшее значение, поскольку полная строка всегда является префиксом самой себя.

Визуализируйте алгоритм здесь:https://personal.utdallas.edu/~besp/demo/John2010/z-algorithm.htm

Ниже приведено решение того же самого:

public static int[] computeZ(String s) {
    int l = 0; r = 0;
    int [] Z = new int[len];
    int len = s.length();
    for (int k =0 ; k < len; k++ ) {
        int j;
        if (k < r) {
            j = (z[k-l] < (r-k)) ? z[k-l] : (r-k)
        } else {
            j = 0;
        }
        while (k + j < len) {
            if (s.charAt(k+j) == s.charAt(j)) {
                j++;
            } else {
                break;
            }
        }
        if (k + j > r) {
            l = k;
            r = k + j;
        }
    }
    Z[0] = len;
    return Z;
}