Дистанционная подготовка: Алгоритмы на строках
Алгоритмы на строках
от Роман Захаров - Суббота 17 Ноябрь 2007, 01:03
  Меня интересуют алгоритмы на строках это КМП и z-алгоритм расскажите о них подробней дайте понятные хорошие ссылки на материалы и пожалуйста раскажите сами алгоритмы и приведите пожалуйста задачи которые они решают задачи (примеры) на которых можно потренироваться заранее благодарен!
Re: Алгоритмы на строках
от Борис Василевский - Суббота 17 Ноябрь 2007, 19:49
  Про КМП можно постараться почитать на алголисте
http://algolist.manual.ru/search/esearch/kmp.php
но лучше почитать книги.
В "Алгоритмы: построкние и анализ" Кормена, Лейзерсона и Ривеста этот алгоритм есть. Однако там нет ничего про z-функцию.

Про нее можно почитать в разборе задачи "A-функция от строчки" по адресу
http://olympiads.ru/moscow/2005/zaoch/archive.shtml
но лучше прочитать "Строки, деревья, последовательности в алгоритмах" Дэна Гасфилда. Там много хороших алгоритмов на строки.

Обе эти книги довольно нетрудно найти в Москве, насколько я знаю.
Re: Алгоритмы на строках
от Роман Захаров - Воскресенье 18 Ноябрь 2007, 21:27
  Спасибо за ответ не могли бы вы написать список задач на которых можно потренироваться по этим алгоритмам(Z и КМП) желательно что б это были задачи которые я бы мог сдать чтоб закрепить тему и с разбором некоторых более сложных задач
Re: Алгоритмы на строках
от Владимир М. Гуровиц - Воскресенье 18 Ноябрь 2007, 22:25
 

Со временем такие материалы безусловно появятся на сайте - но сделать все сразу мы не можем просто физически: сайт сейчас активно развивается, каждый день на нем появляются новые материалы

Re: Алгоритмы на строках
от Роман Захаров - Понедельник 19 Ноябрь 2007, 03:00
  На этом сайте это хорошо, ну а на других сайтах подскажите пожалуйста(ну пока здесь нету)!