Манипулирование строкой: вычисление «сходства строки с ее суффиксами»

Question

Для двух строк A и B мы определяем сходство строк как длину самого длинного префикса, общего для обеих строк. Например, сходство строк «abc» и «abd» равно 2, тогда как сходство строк «aaa» и «aaab» равно 3.

Задача состоит в том, чтобы дать алгоритм для вычисления суммы сходств строки S с каждым из ее суффиксов. Например, пусть строка будет: ababaa. Тогда суффиксами строки являются ababaa, babaa, abaa, baa, aa и a. Сходство каждой из этих строк со строкой ababaa составляет 6,0,3,0,1,1 соответственно. Таким образом, ответ 6 + 0 + 3 + 0 + 1 + 1 = 11.

Answer 1

Вы хотите рассмотреть массив суффиксов .Суффиксный массив слова - это массив индексов суффиксов, отсортированных в лексикографическом порядке.В связанной статье в википедии алгоритмы вычисляют LCP (самый длинный общий префикс) при вычислении массива суффиксов.Вы можете вычислить это в O(n), используя сходства с деревьями суффиксов , как показано в этой статье .

ПРИМЕР: Ваша строка ababaa, поэтому суффиксмассив выглядит так:

5 | a
4 | aa
2 | abaa
0 | ababaa
3 | baa
1 | babaa

где число слева - это индекс, с которого начинается суффикс.Теперь довольно просто вычислять префиксы, поскольку все хранится лексикографически.

В качестве примечания, это тесно связано с проблемой самой длинной общей подстроки .Чтобы подготовиться к следующему собеседованию, подумайте о способах его эффективного решения.

Answer 2

Сначала прочтите эту ссылку о z-алгоритме . Решение O (n), основанное на алгоритме из ссылки, реализованной на python:

def z_func(s):
    z = [0]*len(s)
    l, r = 0, 0
    for i in range(1,len(s)):
        if i<=r:
            z[i] = min(r-i+1, z[i-l])
        while (i + z[i] < len(s) and s[z[i]] == s[i + z[i]]):
            z[i] += 1
        if z[i]+i-1 > r:
            l, r = i, z[i]+i-1
    return sum(z)+len(s)