Дерево суффиксов против массива суффиксов для LCS

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

Теперь вы должны быть в состоянии найти длину общего префикса, общего для всех подстрок, начиная с указателей в окне. Это должно быть минимальное значение LCP, встречающееся между указателями в окне. Если вы используете красно-черное дерево, такое как Java Treeset, с ключом, который состоит из значения LCP как наиболее значимого компонента, и некоторого прерывателя связей, такого как сам указатель, как менее значимого компонента, то вы можете поддерживать минимальное значение. Значение LCP в окне по стоимости, приблизительно равной размеру окна журнала на одну настройку окна.