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

[Diusha]

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

[Арташес]

Вот еще одна интересная публикация:

Анализ строк (String Search) - Graham A. Stephen, October 1992.

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

Конечно, за прошедшие годы проводились многочисленные новые исследования и появились многочисленные новые статьи, не вошедшие в этот обзор. Вместе с тем, конец «периода полураспада» приведенных в нем результатов еще очень далек. Я надеюсь, вы прочтете этот материал с пользой и удовольствием.

П.Дубнер
Ноябрь 1999

Содержание достаточно заманчивое:

Код

1. ВВЕДЕНИЕ
2. ЗАДАЧА
    2.1 Определение задачи
3. ОБЗОР АЛГОРИТМОВ
    3.1 Сопоставления строк
    3.2 Расстояния между строками
         3.2.1 Обобщенные задачи
    3.3 Нечеткое сопоставление строк
         3.3.1 Специальные устройства
         3.4 Максимальная повторяющаяся подстрока
4. АЛГОРИТМЫ
    4.1 Поиск образцов
         4.1.1 Наивный подход
         4.1.2 Кнут-Моррис-Пратт
         4.1.3 Бойер-Мур
         4.1.4 Бойер-Мур-Хорспул
         4.1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
         4.1.6 Хьюм и Сандей.Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
         4.1.7 Харрисон
         4.1.8 Карп-Рабин
    4.2 Расстояние между строками и самая длинная общая подпоследовательность
         4.2.1 Вагнер-Фишер
         4.2.2 Хиршберг
         4.2.3 Хант-Шиманский
         4.2.4 Машек-Патерсон
         4.2.5 Укконен
         4.2.6 Самая тяжелая общая подпоследовательность
    4.3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК
          4.3.1 k несовпадений - Ландау-Вишкин
          4.3.2 k различий - Ландау-Вишкин
    4.4 Самая длинная повторяющася подстрока
          4.4.1 Наивный подход
          4.4.2 Суффиксные деревья
5. НАЗАД, К ИСХОДНОЙ ЗАДАЧЕ
   5.1 Система
   5.2 Задача
6. ПРИЛОЖЕНИЕ A: АСИМПТОТИЧЕСКАЯ ЗАПИСЬ
7. ЛИТЕРАТУРА

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