Алгоритм поиска минимальноого периода строки Опции

[Diusha]

Знаю, что такие есть, знаю, что это одна из стандартных задач на олимпиадах по программированию. Но найти не могу. Гугл не захотел помочь.
Может кто чем поможет? Хотя бы название или фамилию автора.
Алгоритмы с хешированием не подойдут, т.к. подстрока может повторяться не точно

[Арташес]

Обнаружил специализированный ресурс - http://www.itman.narod.ru/. Много полезного.

Вот еше:

Fast and Practical Approximate String Matching (1992).

Солодков, А.Ю. Идентификация сложных объектов нечисловой природы в СУБД с наличием ошибок и пропусков данных [Электронный ресурс] / А.Ю. Солодков. - Саратовский государственный технический университет, 2003. Режим доступа: ]http://iu4.bmstu.ru/konf/2003/sbornik/s2_29.doc

Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. – М.: Мир, 1987. – 120 с.:ил.

Ниман, Томас Сортировка и поиск: Рецептурный справочник / Томас Ниман. – М.: Вильямс, 1998. – 62 с.

Смит, Билл Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычислений / Билл Смит. – М.: Вильямс, 2006. - 496 с.:ил.

Гасфилд, Дэн Строки, деревья и последовательности: Пер. с англ. / Дэн Гасфилд. – СПб.: Невский Диалект; БХВ-Петербург, 2003. – 654 с.:ил.

Цыганов, Н.Л. Обзор алгоритмов нечёткого сопоставления записей применительно к задаче исключения дублирования персональных данных [Электронный ресурс]/ Н.Л. Цыганов, М.В. Марковский. - Московский инженерно-физический институт, 2006. – Режим доступа: http://www.library.mephi.ru/data/scientifi.../t15/1-1-25.doc

Сообщение отредактировал Арташес - Jan 7 2011, 14:57

[Diusha]

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

Было бы чего вспомнить, вспомнил бы

Спасибо, Арташес, много интересного, покопаюсь

[Oldring]

Можно уточнить задачу.
Найти алгоритм поиска минимального периода в строке, работающий быстрее (в среднем, в худшем), чем O(L*T), где L - длина строки, T - минимальный период подстроки

И протестировать алгоритм на следующей строке:

ababbababbabababbababbab

т.к. подстрока может повторяться не точно

И какой критерий "повторения неточно"?

[Diusha]

Можно уточнить задачу.
Найти алгоритм поиска минимального периода в строке, работающий быстрее (в среднем, в худшем), чем

Само собой, о т.н. наивном поиске речи не идет, "время - деньги"

И какой критерий "повторения неточно"?

Критерий такой:
1) если вместо "а" в следующем периоде в той же позиции не "а", а где-то между "а" и "b", скажем "а с половиной", то считаем, что совпадение есть. А если "а и 6 десятых", то уже нет.
2) Могут быть лишние буквы. При их доле меньше чем, считаем, что период не нарушен.
На самом деле речь не о строке как таковой, из букв. Вместо букв - пары чисел.
Если бы требовалось найти заданную "подстроку" в "строке" (в смысле последовательности чисел), то алгоритм КМП (Кнута-Морриса-Пратта) можно было бы модифицировать и для моего случая и префикс-функцию считать не как целую, а как вещественную.
Откопав алгоритм поиска периода, может удалось бы и его модифицировать. Но может - нет. Пока не нашел, не знаю.