Поиск трех равных подстрок равной длины

Question

Учитывая строку S, мне нужно найти три одинаковые подстроки равной длины. Каждая из трех строк не должна перекрываться. Также, если три строки A, B, C, то S не может быть A + B + C. Только условие для удержания - это префикс, B должен находиться между ними, а C - суффикс.

Какова максимальная длина каждой строки.

Пример: Пусть строка S = «aaaaaa», а затем ответ будет 2. Как решить эту проблему, пожалуйста, помогите. Пояснение: Сторона префикса будет aa {1, 2}. Сторона суффикса будет aa {6, 7}, а между частью будет aa {3, 4} или aa {4, 5}.

Возможно ли решение проблемы (N) для этой проблемы? Или если не самый лучший алгоритм сложности, который можно предложить.

Answer 1

Я думаю, что эту проблему можно легко решить с помощью префикса .

Рассмотрите строку S[1 .. N]. Прежде всего, давайте вычислим префикс . После этого шага мы имеем массив P[1 .. N], где P[i] - это длина самого большого суффикса подстроки S[1 .. i], которая соответствует его префиксу, P[i] < i.

Тогда нам просто нужно перебрать всю строку. На каждые i, i = 2 .. N - 1 мы предполагаем, что средняя строка заканчивается в позиции i.

В то же время P[i] самый длинный суффикс S[1 .. i], который соответствует его префиксом и P[N] самый длинный суффикс S[1 .. N], который соответствует его префиксом.

Также обратите внимание, что наши подстроки не могут пересекаться. Таким образом, для S[1 .. i] длина самого длинного суффикса, которая соответствует префиксу и может быть необходимой подстрокой, равна min(P[i], i/2). Для S[1 .. N] длина самого длинного суффикса, которая соответствует префиксу и может быть необходимой подстрокой, ограничена min(P[N], N - i).

Так что за каждые i, i = 2 .. N - 1 мы можем уточнить ответ min(min(P[i], i/2), min(P[N], N - i)), пытаясь получить максимум.

Это решение имеет желаемую линейную сложность.

Например, если исследованная строка равна "aaaaaa", то P является [0, 1, 2, 3, 4, 5].

После этого мы пытаемся обновить ответ:

i = 2 min(min(1, 2/2), min(5, 6 - 2)) = 1 
i = 3 min(min(2, 3/2), min(5, 6 - 3)) = 1 
i = 4 min(min(3, 4/2), min(5, 6 - 4)) = 2 
i = 5 min(min(4, 5/2), min(5, 6 - 5)) = 1 

Таким образом, ответ на 2.