Поиск общих подстрок двух текстов(||строк)

[NixonKNR]

Всем привет!
Я нашел 2 алгоритма решающих эту задачу:
1. Алгоритм Шинглов - http://www.codeisart.ru/python-shingles-algorithm/
2. Наивный алгоритм - http://ru.wikipedia.org/wiki/%D0%9D%...BE%D0%BA%D0%B0
Для полного счастья мне нужен еще один)
Замечание: Общая подпоследовательность не то же самое что общая подстрока. Общие элементы должны идти подряд.
Если кто знает, подскажите, пожалуйста. Заранее спасибо!

через суффиксные деревья можно.
пусть s, t - строки. строишь дерево для строки s$t#, где $, # - спецсимволы, не встречающиеся в исходных строках. обходишь дерево, помечаешь в поддеревье каких вершин есть $ или #, потом выбираешь самую глубокую из вершин, содержащих и $ и #, это и есть ответ.

[NixonKNR]

Суфиксные деревья - интересное предложение. Скорее всего мне подойдет. Сейчас начну изучать эту область. Правда вконце думаю будут проблемы с выделением(подчеркиванием) совпавшего текста...ну и хрен с ним)

[NixonKNR]

Правда вконце думаю будут проблемы с выделением(подчеркиванием) совпавшего текста...ну и хрен с ним)

а не, сор. "Номер суффикса является индексом его начала в тексте"
Короче, кому надо, вот подробное и графическое описание алгоритма, предложенного человеком, который способен трезво мыслить в начале четвертого
http://yury.name/internet/01ianote.pdf 3 стр.

[cat_baxter]

Вот это не подойдет?

http://code.google.com/p/google-diff-match-patch/

и где там решение озвученной задачи?

для diff'ов всяких вообще нужна наибольшая общая *подпоследовательность*, а не подстрока, и ТС ясно сказал, что нужна подстрока, а не наоборот.

[NixonKNR]

что значит mach и path я особо не разбирался, а вот diff, судя по "Demo diff", решает поставленную задачу. Осталось его запустить...