LINUX.ORG.RU

Наибольшая общая подстрока

 ,


0

4

В детстве читал, кажется, у Перельмана (или в другой книжке по математике для детей), про алгоритм нахождения наибольшей общей подстроки у двух строк.

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

Может, кто-нибудь что-нибудь знает/помнит?

Ответ на: комментарий от disarmer

Там нарисован примитивный алгоритм за O(n×m) времени и памяти.

proud_anon ★★★★★ ()

Википедия предлагает только суффиксное дерево или динамическое программирование с таблицами

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

anonymous ()
Ответ на: комментарий от anonymous

кстати там не обязательно хранить всю таблицу, достаточно двух последних строк

Вот это уже похоже.

leakyleaf ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.