Функция примерно такая:
// простой поиск образца в строке
// возвращает индекс начала образца в строке или -1, если не найден
int find(char *образец, char *строка)
{
// i-с какого места строки ищем
// j-с какого места образца ищем
for (int i=0;строка[i];++i) {
for (int j=0;;++j) {
if (!образец[j]) return i; // образец найден
if(строка[i+j]!=образец[j]) break;
}
// пока не найден, продолжим внешний цикл
}
// образца нет
return -1;
}
Простой случай поиска
'игла' — образец
'стогистогстогигстогстогиглстогстогигластогигластог' — строка поиска
Сложный случай поиска
aabbaab
aabaabbaaabaabaabaabaabbaabb
Функция работает и довольно шустро, если образцы и строка «хорошие». Хорошие — это когда внутренний цикл прерывается быстро (на 1-3 шаге, скажем, как в простом случае). Но если образец и строка содержат часто повторяющиеся вложенные куски (как сложном случае выше), то внутренний цикл обрывается ближе к концу образца и время поиска оценивается как О(<длина образца>*<длина строки>). Если длина строки 100тыс, а длина образца 100, то получаем О(10млн). Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.
А если строка — это длинный текст, а образец-фрагмент слова, и надо найти все вхождения этого фрагмента, причем на лету, по мере набора слова (замечали, как быстро это делают браузеры)? Алгоритм КМП находит все вхождения образца в строку и его скорость О(<длина образца>+<длина строки>), поэтому на больших текстах/образцах или на слабых процессорах (как в низкобюджетных сотовых) он вне конкуренции.
А теперь посмотрим на заголовок? Почему «маленькое»? Потому, что изюминка КМП — это префикс-функция, а она действительно маленькая. А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.
Для того, чтобы понять, что и как делает префиксная функция, посмотрим на сложную строку
| a | a | b | a | a | b | a | a | a | a | b | a | a | b | а | a | a | b |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 3 |
Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим строки-префиксы (подстрока, начинающаяся с первого индекса строки) и суффиксы (подстрока, последний символ которой в строке в позиции 7 ( это «наш» символ a) длины K.
| K | префикс | суффикс | |
| 1 | а | a | тут все просто: префикс — это первый символ строки, а суффикс-наш символ a |
| 2 | aa | ba | |
| 3 | aab | aba | |
| 4 | aaba | aaba | самое длинное совпадение, причем здесь и ниже суффикс и префикс начали перекрываться (как фрагменты строки поиска) |
| 5 | aabaa | baaba | |
| 6 | aabaab | abaaba |
Обратите внимание: для длины 4 суффикс (как последовательность символов) совпадает с префиксом и это максимальное значение K при котором суффикс совпадает с префиксом. Именно оно и заносится в соответствующую позицию (7) массива длин префиксов.
Можно заметить, что для K=7 префикс тоже совпадет с суффиксом, поскольку это одна и та же строка. Но этот тривиальный случай нам не подходит, т.к. для работы алгоритма нужны именно подстроки.
Обозначим S-исходная строка, S(n) -начало (префикс) строки S длины n, S[n]-символ в позиции n строки S. M[n] значение в массиве, S(M[n])- та самая строка, которая являемся префиксом и суффиксом максимальной длины для позиции n (для краткости обозначим её P(n)). Строка P(n) как бы «виртуальная», она не формируется и никуда не пишется. Это просто начальный фрагмент1 исходной строки S длины M[n]. И этот начальный фрагмент1 совпадает (как последовательность символов) с фрагментом2 длины M[n], последний символ которого в позиции n. Если M[n]=0, то совпаденией нет.
Имеем: позиция 7 массива заполнена значением М[7]=4, самая длинная строка P(7)='aaba' длины 4 (естественно), надо перейти к позиции 8 и заполнить M[8]. Можно тупо посчитать все префиксы и суффиксы длиной от 1 до 7, сравнить их и записать максимальную длину в позицию 8. Но мы пойдем другим путем (вслед за КМП). Пусть найдена максимально длинная строка P(8) длины k, которая префикс и суффикс для позиции 8. Строка p7 из первых k-1 символов является префиксом и суффиксом для позиции k-1. Не факт, что для 7й позиции она самая длинная. Однако, если оказалось, что p7=P7, то P8 — это расширение P7 на один символ. Чтобы проверить, можно ли расширить P7 на одну позицию, надо проверить, совпадает ли добавляемый в суффикс символ (это символ S[8]=a) со следующим символом префикса. Следующий символ префикса a находится в позиции М[7]+1=5 (подумайте, почему так). Если совпал (а в нашем случае он совпал), то задача выполнена — М[8]=М[7]+1, а P(8)=P(7)+символ в 8 позиции S[8]=a. Получаем P(8)='aabaa'. При успешном расширении надо всего одно сравнение для вычисления очередного значения массива. Кстати, отсюда следует, что при движении вдоль массива значения могут возрастать максимум на 1.
Для удобства повторю сложную строку, чтобы не нужно было перемещаться вверх-вниз.
| a | a | b | a | a | b | a | a | a | a | b | a | a | b | а | a | a | b |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 3 |
Для нашей строки P(8) — это просто расширение P(7) на один символ, понадобилось 1 сравнение. Однако P(8) не удалось расширить до P(9), поскольку S[9]=a, а S[M[8]+1=6] =b. Раз не подошел префикс P8 длины M[8]=5, пробуем префикс длины M[5]=2. Он тоже не подходит: S[2+1] =b. Пробуем префикс длины M[2]=1 и его можно расширить, т.к. S[1+1] =a. Поэтому M[9]=2, на единицу больше длины расширяемого префикса. Для заполнение M[10] надо 2 сравнения (можете проверить). А вот чтобы заполнить элементы с 11 по 17, понадобится по одному сравнению. В результате расчет значений массива занимает время порядка О(длина строки).
Итак, с алгоритмом заполнения более-менее ясно.
Переходим к трюку.
Для нахождения образца ааbаа в строке ааbааbааааbааbаааb склеим образец со строкой вот так ааbаа@ааbааbааааbааbаааb и вызовем для нее префикс-функцию для заполнения массива.
| a | a | b | a | a | @ | a | a | b | a | a | b | a | a | a | a | b | a | a | b | а | a | a | b |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 3 |
Префикс-функция
А теперь примеры префикс-функции. Отличие от описания выше в том, что, как принято в Си-языках, индексы считаются с 0.
Пример на C++
Функция возращает вектор длин префиксов строк, а строка передается как string (не надо вычислять длину)
vector<size_t> prefix_function (string s)
{
size_t n = s.length();
vector<size_t> pi(n); // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для построки длины i.
// p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых
for (size_t i=1; i<n; ++i)
{
size_t j = pi[i-1];
while ((j > 0) && (s[i] != s[j])) // не равны
j = pi[j-1]; // берем ранее рассчитанное значение (начиная с максимально возможных)
if (s[i] == s[j]) // равны
++j;
pi[i] = j;
}
return pi;
}
Пример на C
Функция ничего не возвращает. Первый параметр — указатель на строку, второй — указатель на заполняемый массив длин префиксов, третий р — длина строки и массива.
// если компилятор не понимает size_t, замените на int
void prefix_function (char *s, int *pi, size_t n)
{
pi[0]=0; // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для построки длины i.
// p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых
for (size_t i=1; i<n; ++i)
{
int j = pi[i-1];
while ((j > 0) && (s[i] != s[j])) // не равны
j = pi[j-1]; // берем ранее рассчитанное значение (начиная с максимально возможных)
if (s[i] == s[j]) // равны
++j;
pi[i] = j;
}
}
Этот код добавлен по результатам обсуждения
// пример функции обработки, которая выводит индекс начала найденного образца
int f(size_t i)
{
printf("%d\n",i);
return 1;
}
// str строка поиска
// obr образец, который ищем
// pi массив длин префиксов для образца (минимум столько элементов, сколько символов в образце)
// int f(size_t i) когда образец найден, вызывается эта функция. Еи передается индекс начала найденного в str образца
// функция возвращает 0, если надо прекратить поиск и 1, если надо продолжить
void prefix_find (char *str, char *obr, size_t *pi, int (*f)(size_t))
{
pi[0]=0; // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для построки длины i.
// p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых
size_t l; // длина образца
// заполняем массив длин префиксов для образца
for (l=1; obr[l]; ++l)
{
size_t j = pi[l-1];
while ((j > 0) && (obr[l] != obr[j])) // не равны
j = pi[j-1]; // берем ранее рассчитанное значение (начиная с максимально возможных)
if (obr[l] == obr[j]) // равны
++j;
pi[l] = j;
}
size_t j=0; // длина префикса для последнего обработанного элемента
for (size_t i=0; str[i]; ++i)
{
while ((j > 0) && (str[i] != obr[j])) // символ строки не совпал с символом в образце
j = pi[j-1]; // берем ранее рассчитанное значение (начиная с максимально возможных)
if (str[i] == obr[j]) // есть совпадение
++j; // увеличиваем длину префикса на 1
if (j==l)
if (!f(i-l+1)) return; // образец найден, вызовем функцию обработки
}
}
Мой рассказ о маленьком чуде — алгоритме КМП подошел к концу. Конечно, эта статья о КМП далеко-далеко не первая и наверняка не последняя. Вот две статьи здесь, на хабрахабр: Поиск подстроки. Алгоритм Кнута–Морриса-Пратта и Поиск подстроки и смежные вопросы.
Но я надеюсь, кто-то посчитает эту статью полезной для себя, а кто-то (ведь может такое случиться) станет применять КМП. Даже если он не вполне разобрался с внутренним механизмом его работы (разобраться никогда не поздно).
Алгоритм КМП не единственный быстрый алгоритм поиска, но он достаточно быстрый (для задач типа олимпиадных) и при этом простой. Алгоритм Бойера-Мура близок к КМП по сложности и для определенного круга задач (где образец не содержит повторяющихся фрагментов) он быстрее. Но зато для другого круга задач (где образец и строка поиска содержат повторяющиеся последовательности, как в примерах к статье) он заметно уступает КМП. Наконец, есть задачи, где выбор того или другого — дело вкуса (о которых не спорят). В некоторых случаях (или даже областях) алгоритм Ахо — Корасик может оказаться эффективней и КМП и Бойер-Мура. Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо.
Дополнение по результатам обсуждения
Можно модифицировать префикс-функцию, чтобы она использовала буфер не О(длина строки+длина образца) а О(длина образца). В этом случае память нужно выделить только для хранения длин префиксов образца, а длины префиксов строки поиска не запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), префикс-функция вызывает функцию обработки найденного фрагмента. Модифированная функция prefix_find добавлена в статью. Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кому-то может понадобиться.
На возможность сэкономить память обратил мое внимание mayorovp и он же дал ссылку в своем сообщении на реализацию варианта префикс-функции, которая выводит позиции найденных фрагментов в cout.
По замечанию staticlab изменил тип переменных на size_t (так действительно будет корректнее).
Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях:
Последняя иллюстрация — взгляд «с высоты птичьего полета» на префиксы-суффиксы строки
habrhabhabrhabrhabrhabhabrhabhabrhabhabrhabrhabrhabhabrhabra
без массивов индексов и длин.
Комментарии (53)
ZlodeiBaal
06.08.2016 17:02+9Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.
Я вас огорчу. Вокруг таких реальных задач вся биоинформатика крутиться. Там масса алгоритмов разработано именно для анализа строк ДНК.
zelserg
06.08.2016 17:19+1Вы меня не огорчили — я в курсе. Это популярная статья для программистов, которым просто нужен быстрый поиск. Процитирую себя: «Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо».Специалисты по ДНК (или по поиску вирусных сигнатур) относятся именно к тем, на кого это статься не ориентирована.
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
olegchir
06.08.2016 18:27+3присоединюсь ZlodeiBaal, лучше кроме «олимпиадного програмирования» там в статье привести еще какие-то примеры, когда такие вещи нужны на самом деле
Anvol
07.08.2016 15:47+1Позволю добавить, КМП примечателен отсутствием сдвига указателя чтения «назад», тем самым позволяя просматривать поток данных.
Префикс-функция, о которой велась речь в статье, выстраивает конечный автомат, по которому движется алгоритм при поиске подстроки. Это позволяет переложить такой алгоритм на ASIC/FPGA и сферу применения — intrusion detection systems, где данных много, да еще и хранить их для дальнейшего анализа не всегда возможно.
mayorovp
06.08.2016 17:43+3В результате расчет значений массива занимает время порядка О(длина строки).
А где доказательство?
А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.
Почему задача, которую он решает, названа "вроде как совсем другой", если это прямое обобщение исходной задачи?
Для нахождения образца ааbаа в строке ааbааbааааbааbаааb склеим образец со строкой вот так ааbаа@ааbааbааааbааbаааb и вызовем для нее префикс-функцию для заполнения массива.
… и сразу же повысим требования по памяти в несколько раз! Дополнительной памяти правильная реализация алгоритма требует O(N), где N — длина образца. Ваш же способ требует O(N+M) дополнительной памяти, где N — длина образца, M — длина текста.
zelserg
06.08.2016 18:23-3Даже не заню, что Вам ответить: наверное эта статья не для Вас. Раз требования к памяти возрастают в несколько раз, то Ваши образцы в несколько раз больше строки, где они ищутся.
zelserg
06.08.2016 18:35К сожалению, я неправильно понял Ваше замечание, а редактироване заблокировано. Можете дать ссылку, где памяти требуется O(N)?.. Во всех задачах на acmp, timus (где я использовал КМП) проблем ни с памятью ни со скоростью не было. Но все же интересно.
mayorovp
06.08.2016 18:49Там, вероятно, и вовсе нет задач где можно так запросто упереться в ограничения, особенно при работе с текстом. Но привычка совершать лишние действия может тяжело аукнуться при попытке решения какого-нибудь "гроба".
zelserg
06.08.2016 19:30Так все-таки есть ссылка на O(N) или нет?
mayorovp
06.08.2016 20:05+2Я, наверное, вас не так понял. Вам ссылку на задачу надо или на алгоритм? Если второе — то вот: https://ideone.com/qmNQ39
zelserg
06.08.2016 20:27Спасибо, завтра поизучаю.
staticlab
06.08.2016 21:15+2Из алгоритма ведь очевидно, что достаточно выделить памяти в размер образца n, поскольку из всего множества M[i], i > n может понадобиться только предыдущее значение, которое можно хранить в простой переменной.
Ещё резануло глаз:
int n = (int) s.length(); vector<int> pi (n);
length() возвращает значение типа size_t, а конструктор вектора принимает первым аргументом именно size_t.
zelserg
06.08.2016 21:28Я понял (а точнее, даже вспомнил). В случае, когда надо найти не все вхождения подстроки, а первое вхождение, память нужно выделить для хранения длин префиксов образца. А длины суффиксов строки поиска на запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), функция прекращает работу и возвращает найденную позицию.
lemelisk
06.08.2016 23:37Нет никакой разницы нужно ли найти первое вхождение или же все вхождения. Код, предложенный вам выше, ищет все вхождения (роль @ в нем играет
'\0'на конце образца)zelserg
07.08.2016 07:11Код выводит информацию об нахождении в cout. Получается, что он «заточен» под определенную задачу. С массивом проще — вызывающая прощедура сама решает, что делась с найдеными фрагментами и делает. Хотя можно модифицировать префикс-функцию так, чтобы ее передавала функция, обрабатывающая найденный фрагмент.
Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.lemelisk
07.08.2016 12:16+1Возвращайте вектор позиций вхождения или вы считаете, что функция поиска подстроки должна возвращать в качестве ответа массив вычисленных префикс-функций?
mayorovp
07.08.2016 13:43В чем проблема вместо вывода в
coutделать что-то еще?
Или вы имеете в виду, что в данной реализации алгоритма не хватает выделения самого алгоритма? Тогда можно сделать вот так: https://ideone.com/zn9Fe4
Или вот так: https://ideone.com/pnafkx
Или еще кучей других способов. Алгоритм от этого не изменится, это лишь оформление.
staticlab
07.08.2016 18:49+1Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
А если потребуется найти что-то в многогигабайтном файле?
zelserg
07.08.2016 22:31На домашнем компьютере 200+ Гиг в память не затянешь, по-любому придется считывать порциями. Будет порция 20-50-100Мб особой роли не играет. 30 Гиг я читал сам и работал с программами воосстановления файлов на разделах под терабайт. Они тоже читают порциями, правда неясно, какой алгоритм используют.
Ну а если встретится задачка, где будут жесткие ограничения по памяти и скорости — так я добавил в статью процедуру prefix_find, которой нужен буфер только под образец.
Large
07.08.2016 13:23В результате расчет значений массива занимает время порядка О(длина строки).
В худшем случае это S = sum(ln k, 1, n) и это не линейное время так как предел lim S/n видимо бесконечный.mayorovp
07.08.2016 13:54+2Э… там вообще-то и в худшем случае линейное время, просто автор поста не стал это доказывать.
Мы не можем уменьшать текущий префикс большее число раз, чем увеличивали. А увеличиваем мы его только на 1 и не чаще 1 раз на символ из текста и шаблона. Отсюда и оценка времени O(N+M)
Large
07.08.2016 14:47Точно, мы ж не до конца каждый раз спускаемся, просчитался, спасибо за уточнение.
buriy
06.08.2016 17:57+1А почему тогда не алгоритм Бойера-Мура, который настолько же сложно объясняется, но часто работает быстрее в несколько раз? (до N раз быстрее, где N — длина образца — хотя иногда, надо признать, может работать и медленнее, чем КМП — худшая оценка у него выше)
(Если первый символ в КМП не совпадает, мы всегда смещаемся на единицу, если последний символ в БМ не совпадает, и этого символа нет в образце — мы смещаемся сразу на длину образца! И даже если есть одинаковые символы, мы почти всегда смещаемся больше, чем на единицу).zelserg
06.08.2016 18:20+7Написал бы про Байера-Мура — обязательно кто-то спросил бы «прочему не КМП — он ведь такой-разтакой»? Я захотел написать про КМП и написал. Вам нравится Баейр- Мур — так напишите! Зачем противопоставлять одно другому? Чем больше интересных/полезных статей — тем лучше.
buriy
06.08.2016 19:07+1Ок. Но я был бы признателен, если бы вы хотя бы упомянули его в вашей статье рядом с алгоритмом Ахо-Карасик.
zelserg
06.08.2016 19:54Ну, если только упомянуть — так я внес дополнение. Вы удовлетворены? Все же это статья про алгоритм КМП, а не монография про различные методы эффективного поиска.
buriy
07.08.2016 15:01+1Спасибо большое. Я просто считаю, что всегда, описывая определённое решение, нужно указать область применимости, недостатки алгоритма и альтернативные решения.
Кстати, теперь я понимаю, почему вы не любите алгоритм Бойера-Мура — вы не считаете, что он существенно быстрее в большинстве случаев :) А, между тем, в grep используется именно Бойер-Мур, и именно из-за его более высокой скорости.
Объяснение ваше в посте про БМ некорректное. БМ тем медленнее, чем больше частичных совпадений между концом образца и текстом, а не внутри образца. Но его можно улучшить, чтобы этого замедления не было, и тогда худшая оценка будет совпадать к КМП. Получится как с быстрой сортировкой против сортировки вставками.
Поскольку редко кто в 2016м году подобные алгоритмы программирует сам вручную, я бы не рекомендовал на практике КМП, а рекомендовал БМ или Ахо-Карасика.
А для знакомства с алгоритмами рекомендовал бы Кормана вместо Хабрахабра :)mayorovp
07.08.2016 15:24+2Кхм, вообще-то алгоритм Ахо-Карасика решает другую задачу, его с КМП и БМ сравнимать некорректно.
buriy
08.08.2016 00:42Правильно, алгоритм Ахо-Корасика решает расширенную задачу, когда шаблонов много, но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика, и заодно немного сэкономить на группировке шаблонов в готовый trie.
mayorovp
08.08.2016 09:08Вообще-то, алгоритм Ахо-Корасика — это и есть КМП, расширенный на насколько образцов :)
buriy
08.08.2016 10:22Хм, покажите, где я утверждаю обратное :)
mayorovp
08.08.2016 11:03+1но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика
Нельзя взять алгоритм Ахо-Корасика вместо раширенного на несколько образцов КМП — потому что это один и тот же алгоритм.
zelserg
07.08.2016 16:07-1Я пользовалсся Бойер-Муром, но при решении одной из задач все время выскакивал TL. В обсуждениях я прочитал, что надо использовать КМП (в строке поиска и в образце были часто повторяющиеся фрагменты и Б-М не мог быстро «скакать», как я понял из обсуждения). Почитал про КМП, запрограммировал и задача прошла «на ура», а сам КМП запал в душу. Это было давненько, с тех пор я стал использовать его и больше никогда TL не встречался (по причине медленного поиска). Наверное потому, что олимпиадные задачи не требуют чего-то более серьезного.
mayorovp
07.08.2016 16:45+1Потому что, как я уже писал ранее, использовать БМ без турбосдвига нельзя.
lemelisk
07.08.2016 19:04-1Для олимпиадных целей (цель — написать как можно проще, лишь бы попадало в требуемую асимптотику) самый простой алгоритм — это поиск с помощью хеш-функции. Особенно когда нам нужно найти только первое вхождение, тогда нам не обязательно верить, что если хеш-функции двух строк равны, то эти строки совпадают.
zelserg
07.08.2016 22:39С использованием хешей не самый простой, и не самый быстрый, особенно при поиске одного шаблона. Вот когда шаблонов много — тогда стоит подумать об алгоритме Рабина-Карпа, например.
lemelisk
08.08.2016 00:28Да, я именно про Рабина-Карпа и говорил (забыл, что у него есть устоявшееся название). А почему не самый простой то? По объему кода сопоставим с КМП, зато идея, лежащая в его основе, гораздо проще. И при этом довольный мощный: обобщается для двумерного случая (найти за O(n*m) все вхождения заданного шаблона прямоугольника в квадратной матрице n*m), для случая множества шаблонов.
lemelisk
08.08.2016 01:02+1Я вам что-то сначала поверил, а теперь осознал, что не понимаю, как он обобщается на случай множества шаблонов нефиксированной длины.
buriy
08.08.2016 00:58Понятное дело, для олимпиад специально придумают контрпримеры, чтобы использовать алгоритм O(MN) вместо O(M+N) было нельзя. Наиболее простой контрпример — шаблон и строка из одинаковых букв («ааааа» и «аааааааааааааааа»). Нужна модификация БМ с турбосдвигом, которая работает за 2*N в худшем случае, хотя, конечно, она сложнее.
Но подумайте вот о чём. Олимпиады — это лишь тренировка навыков скоростного программирования, а не практика написания программных продуктов.
Для написания реальных программных продуктов нельзя использовать те же самые критерии, что и для олимпиад.
Поэтому лучше брать готовые алгоритмы, упакованные в библиотеки. Конечно, крайне желательно понимать, как они работают, чтобы знать их ограничения. Спасибо вам за хорошо иллюстрированный пост, я уверен, он поможет многим разобраться, что происходит. Но лучше думайте о промышленных программистах, которые будут использовать ваш пост, как руководство к действию — а нам всем потом именно их программами придётся пользоваться…
zelserg
07.08.2016 16:16+1Насчет grep не знаю, а вот что используют программы типа WinHex, работающие с разделами, восстановлением файлов, когда надо прокачать десятки (а то и сотни) гигабайт данных — интересно.
mayorovp
06.08.2016 18:54+2Зато КМП легко расширяется для нескольких образцов — а алгоритм Бойера-Мура нет.
Да и сложность в худшем случае может сыграть злую шутку, поэтому без эвристики турбосдвига алгоритм Бойера-Мура лучше не использовать. А с этой эвристикой алгоритм становится намного сложнее КМП.
ZaMaZaN4iK
07.08.2016 04:04+1
inoyakaigor
07.08.2016 13:01А объясните неучу как формируется массив длин префиксов?
lemelisk
07.08.2016 19:47В статье про это есть, правда без доказательств и оценки асимптотики. Если очень вкратце, то пусть
l(S)— это префикс-функция строкиS(для удобства восприятия будет считать значением функции саму строку, а не её длину, т.е.l(ababa)=aba). Тогда:
1) Все (не только самый длинный) собственные префиксы, являющиеся также и суффиксами, строкиS— это множествоl(S),l(l(S)),l(l(l(S)))… (до тех пор, пока не получим пустую строку. Будем считать, что она также является подходящим префиксо-суффиксом).
2) Рассмотрим строкуSc(дописали в конец строки символc). Пустьl(Sc)=Ac(т.к. префикс-функция является суффиксом строки, то если только это не пустая строка, то она обязана заканчиваться нас.Аможет быть пустой строкой). Тогда нетрудно понять, чтоAявляется префиксо-суффиксом (каким-то, не факт, что самым длинным) строкиS.
3) Из этих двух соображений возникает алгоритм нахожденияl(Sc). Будем последовательно перебирать все префиксо-суффиксы строкиS, начиная с самого наибольшего (т.е. просто будем идти по рядуl(S),l(l(S)),l(l(l(S)))...) и проверять не будет ли это также префиксо-суффиксом для строкиSc(для этого необходимо и достаточно, чтобы символ, следующий за концом соответствующего префикса, былс).
Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
encyclopedist
Я не понимаю, почему в таблице в разделе "Переходим к трюку" на позиции 6 (там где '@') стоит 3, а на позиции 8 стоит 5 как будто там найдено совпадение. Нет ли там ошибки?
zelserg
Спасибо за замечание — это проблемы копипаста. Так канительно создавать таблицы. Особенно с цветным выделением, т.к. оно сильно отвлекает внимание. Вроде сейчас поправил.