Поиск наибольшей общей подстроки с помощью суффиксного дерева.

Задание.
Поиск наибольшей общей подстроки с помощью суффиксного дерева.

1. Теоретическая часть.
1.1. Формальные понятия и определения.
Последовательность символов (возможно, пустая) из алфавита обозначается буквами r, s и t и называется строкой. |t| обозначает длину строки t.
Префикс r строки t — строка такая, что rs = t для некоторой (возможно, пустой) строки s.
Суффикс r строки t — строка такая, что sr = t для некоторой (возможно, пустой) строки s.
Суффиксное дерево – это нагруженное дерево, содержащее все суффиксы некоторой строки[1].
Нагруженное дерево – структура данных, представляет собой корневое дерево, у которого для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены. Считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла. В некоторых приложениях удобно считать все узлы дерева выделенными[3].
Таким образом, ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а задаётся положением данного узла в дереве. Получить ключ можно выписыванием подряд символов, помечающих рёбра на пути от корня до узла. Ключ корня дерева — пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые внутренние узлы[3].