В споре рождается истина

Привет.
Что надо делать, если в данном тексте T (text) надо найти строку P (pattern) ?
Варианты:

• Тупой поиск в лоб
• Чуть-чуть более умный поиск (алгоритм Рабина-Карпа), где-то в челюсть
• Поиск на основе конечных автоматов (пусть будет в пупок).
• Модифицированный поиск на основе КА: Алгоритм Кнута-Морриса-Пратта. Да-да, как раз туда.
• Есть еще много-много способов найти что-то в чем-то, например, алгоритм Ахо-Корасик и другие устрашающие комбинации фамилий

Если строка и текст довольно небольшие (пусть до 50 символов) – можно смело использовать первый вариант.
Но лучше даже в такой ситуации применить алгоритм Рабина-Карпа и быть спокойным.

Для более тяжелых случаев понадобится конечный автомат.
Чуть подробнее: мы строим для данного образца конечный автомат.
Состояния обозначаются номерами от 0 до m (длина образца). Если автомат находится в состоянии i, значит на данный момент совпало i символов образца и послендих i символов текста.
Понятное дело, перед поиском надо построить таблицу переходов.

Ну и в конце концов – само совершенство – алгоритм Кнута-Морриса-Пратта.
О нем все так много говорят! Иногда мне даже кажется, что я единственный человек на Земле, который не понял его!

Конечно, я решил исправлять ситуацию. Но, черт возьми, никак не могу врубиться, откуда свалилась эта префикс-функция? Как авторы вдруг догадались ее использовать?

Если вы оказываетесь в подобной ситуации, лучшим выходом будет просто открыть Кормэна, найти, прочитать и понять нужную главу, а потом выполнить упражнения. Если вы не смогли выполнить эти упражнения – значит вы не нашли нужную главу, или не прочитали ее. Ну или не поняли. Но как правило понимание приходит во время решения упражнений.

Есть небольшая деталь. Очень эффективно применять КА или КМП, если есть один шаблон и много текстов. Фактически один раз мы строим таблицу переходов, а потом просто просматриваем тексты за 1 проход и знаем количество вхождений и их “координаты”.

Интереснее другое. Что, если образцов много, а текст – один?
Ну, например, решили выяснить – кто же все-таки отец (из этих 30) данного человека? Я правда не знаю, может там и не поиск подстроки…

Все эта каша-малаша возникла у меня в голове, когда я пытался решить эту задачу:

http://codeforces.com/contest/25/problem/E

А потом я решил сделать еще кое-что.
Вот скриншот (не знаю, где есть нормальный хостинг, чтобы выложить это):

Конечный автомат для поиска образца в тексте

Сделал я это на JavaScript. Для вывода графов использовал какой-то глючный минифреймворк dracula, на который даже ссылку давать не хочу.

Я еще давно понял, что мы с JavaScript созданы не друг для друга. Так что спешу перечислить основные минусы JavaScript:

• Это не Ruby и даже не C++
• Какие-то странные приколы с переменными.
  

  var a = 3;
  b = 2;
  delete b; // можно, удаляется созданное нами же свойство объекта window
  delete a; // нельзя, пытаемся удалить переменную
  

• Пусть есть строка a. Не знаю, почему, но у меня a[i] не ратало. Пришлось делать a.charAt(i)
• Непонятная ситуация с массивами. Например, такой код у меня не работал так, как я ожидал:
  

  var a = [1,2,3];
  for (i in a)
      alert(i);
  

  
  Надо делать так:
  

  var a = [1,2,3];
  for (i in a)
      alert(a[i]);
  

  
  По-моему, довольно странно. Я же не объявлял массив как ассоциативный массив !

К этому надо прибавить невозможность нормальной отладки и разные реакции браузеров на один и тот же код. И да, эта конченая библиотека для рисования графов. Она не позволяет изменять или перерисовывать графы. Формируй граф до загрузки страницы – и никак иначе!

Резюме.
javascript – это совершенно отличный от C++ язык, взять хотя бы прототипы и замыкания.

Поиск подстроки в строке – интересная задача, имеющая не менее интересные алгоритмы решения, в том числе Рабина-Карпа, Ахо-Корасик, конечный автомат, КМП и так далее.