Обработка строк: вычисление «подобия строки с ее суффиксами»

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

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

Пример: Ваша строка ababaa, поэтому массив суффиксов выглядит следующим образом:

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

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

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