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

[Diusha]

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

[ukpyr]

http://algolist.manual.ru/search/lrs/index.php
http://kladovka.net.ru/delphibase/?action=...ch&id=10749
http://www.rsdn.ru/forum/alg/752184.flat.aspx

[Diusha]

К сожалению, опять не то.
Требуется вот что:
Есть строка ABCABCABCABC
Из нее нужно выделить минимальный период: ABC (ABCABC тоже период, но уже не минимальный)
Есть строка ABCxABCyABCzABC.
У этой строки периода нет

[Арташес]

А на сайте Олимпиады по программированию смотрели?

Там в библиотеке, в разделе "Алгоритмы на строках" есть две интересные публикации:

1. "Suffix arrays: A new method for on-line string searches" - Udi Manber, Gene Myers (1991)
   Статья на английском. В ней описан такой мощный инструмент , как суффиксные массивы. Даётся метод с быстродействием O(N * log N) на построение и O(M + log N) на поиск(N - длина строки, в которой ищется подстрока длины М). Алгоритмы которые работают с суффиксными деревьями быстрее, но, как правило, сложнее.
2. "Лекции по информатике" - Дмитрий Павлов (2003)
   Конспект лекций двукратного чемпиона мира по программированию ACM ICPC, проведенных в рамках подготовки школьников Санкт-Петербурга к всероссийским олимпиадам по информатике. Сделана попытка изложить темы и алгоритмы, которые активно применяются в олимпиадах и которые недостаточно хорошо освещены в доступной литературе по информатике: структуры данных (особенно, деревья Фенвика и отрезков), динамическое программирование, поиск подстроки в строке, проективная геометрия, практические замечания и др.

Эти статьи я, на всякий случай, прилагаю.

Прикрепленные файлы

 sfx_array.zip ( 88.65 килобайт ) Кол-во скачиваний: 72
 informatics_lection.ps ( 961.5 килобайт ) Кол-во скачиваний: 25

 

[Diusha]

1. "Suffix arrays:
2. "Лекции по информатике" - Дмитрий Павлов (2003)

1 - поиск ивестной подстроки - не то
Вообще O(N * log N) - больно долго. Видимо, этот алгоритм оправдывает себя в тех случаях, когда в одной строке надо найти кучу образцов (за счет O(M + log N) ). А для разового поиска, по-моему, ничего быстрее КМП не придумали ( O(M+N) на всё - про всё)

2 - пока не сумел посмотреть. Скачал Post Script Viewer, а он .ps не видит
Не пoдскажете, чем .ps смотрите?

[Арташес]

Не пoдскажете, чем .ps смотрите?

Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/

[Diusha]

Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/

Пока вылезают проблема за проблемой. Возможно, я туповат...
Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное?

[Арташес]

Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное?

Есть самый прямой вариант - Adobe Acrobat (вернее, Distiller). Но вообще странно, с Ghostscipt'ом, обычно, проблем не возникает.

[Diusha]

У меня проблемы могут быть везде. Вот и сейчас Акробата установить не могу, т.к. CD-ром сдох (Фокситом пользуюсь)

[Арташес]

Вот и сейчас Акробата установить не могу...

Ладно, в таком случае я предлагаю воспользоваться онлайн конвертором - PS to PDF - The Online Converter. На всякий случай прилагаю уже обработанный Ghostscipt'ом файл.

Прикрепленные файлы

 informatics.pdf ( 464.04 килобайт ) Кол-во скачиваний: 66