Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)

  • Tutorial
Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки. Функция примерно такая:
// простой поиск образца в строке
// возвращает индекс начала образца в строке или -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;
}
Простой случай поиска'игла' — образец'стогистогстогигстогстогиглстогстогигластогигластог' — строка поискаСложный случай поискаaabbaabaabaabbaaabaabaabaabaabbaabbФункция работает и довольно шустро, если образцы и строка «хорошие». Хорошие — это когда внутренний цикл прерывается быстро (на 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
Строка под ней — номер (позиция) символа в строке (для удобства описания алгоритма считаем номер с 1), а самая нижняя строка- массив M длин префиксов, ключ к пониманию префикс-функции.Возьмем символ с номером 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
Теперь другой случай — P8 расширить не удалось, т.е. символ S[9]=a не совпал с символом строки S в позиции M[8]+1=6 b. Суффикс расширяется легко (поскольку новый символ просто дописывается в конец), а с префиксом проблемы, т.к. добавляемый в суффикс символ может не совпасть с очередным символом префикса. Если префикс P(k) не подходит, надо найти другой такой префикс, покороче, у которого такой же суффикс и попробовать расширить его. Но префикс покороче, причем с таким же суффиксом — это S[M[M[k]]), т.к. при заполнении массива М каждый элемент содержит длину максимально длинного префикса с таким же суффиксом. Поэтому, если не удалось расширить S(M[k]) пробуем так же расширить S(M[M[k]]) и т.д, пока не совпадет или пока не получим нулевую длину (тогда очередной символ S надо просто сравнить с 1м символом строки S). Цикл перебора походящих префиксов заканчивается очень быстро, потому, что вся нужная для этого информация уже сидит в массиве М.Для нашей строки 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
Символ '@' играет роль разделителя, его заведомо нет ни в образце, ни в строке поиска (нужно подобрать именно такой символ). Посмотрим на позиции 11, 14, 19, 22 массива. Значения в массиве равны 5, это означает, что суффикс длиной 5 (фрагмент строки поиска) совпадает с 5 символами префикса. А 5 символов префикса — это и есть образец для поиска! Алгоритм поиска получатся такой — склеиваем с помощью разделителя образец и строку поиска, передаем «склейку» префиксной функции и потом ищем в массиве элементы, равные длине образца, Можно заметить, что значений больше длины образца не будет из-за символа-разделителя, а значения, равные длине образца могут появиться только в позициях, соотвествующих исходной строке поиска. Склеенная строка имеет длину <длина образца>+<длина строки>, поэтому время расчета оценивается как О(<длина образца>+<длина строки>), как и говорилось в начале статьи. Объем необходимого префикс-функции буфера равен <длина образца>+<длина строки>, но можно модифицировать префикс-функцию так, чтобы хватило буфера <длина образца> (пример модификации в дополнении)

Префикс-функция

А теперь примеры префикс-функции. Отличие от описания выше в том, что, как принято в Си-языках, индексы считаются с 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; // количество совпавших символов, оно же индекс сравниваемого 
     // символа в образце. В строке сравниваемый символ будет иметь индекс i
     for (size_t i=0; str[i]; ++i) 
     {
это место — ключ к эффективности КМП. Если очередные символы строки и образца не совпали, мы не двигаем образец на 1 символ и не сравниваем его со строкой с самого начала (как в примитивном поиске в начале статьи). Мы сдвигаем образец на несколько символов и делаем одно сравнение str[i] и obr[j]. Если не совпало — опять сдвиг образца, пока символы не совпадут или не дойдем до начала образца. Т.о. по строке поиска назад не двигаемся, только вперед (хотя и с остановками).
        while ((j > 0) && (str[i] != obr[j])) 
// Очередной символ строки не совпал с символом в образце. Сдвигаем образец, 
// причем точно знаем, что первые j символов образца совпали с символами строки 
// и надо сравнить j+1й символ образца (его индекс j) с i+1м символом строки.
            j = pi[j-1];    // если j=0, то достигли начала образца и цикл следует прервать
                  
        if (str[i] == obr[j]) // есть совпадение очередного символа 
            ++j;              // увеличиваем длину совпавшего фрагмента на 1
        if (j==l)
            if (!f(i-l+1)) // образец найден, вызовем функцию обработки
                  return;  // и выйдем из процедуры, если она вернет 0. 
     }
} 
Мой рассказ о маленьком чуде — алгоритме КМП подошел к концу. Конечно, эта статья о КМП далеко-далеко не первая и наверняка не последняя. Вот две статьи здесь, на хабрахабр: Поиск подстроки. Алгоритм Кнута–Морриса-Пратта и Поиск подстроки и смежные вопросы.Но я надеюсь, кто-то посчитает эту статью полезной для себя, а кто-то (ведь может такое случиться) станет применять КМП. Даже если он не вполне разобрался с внутренним механизмом его работы (разобраться никогда не поздно). Алгоритм КМП не единственный быстрый алгоритм поиска, но он достаточно быстрый (для задач типа олимпиадных) и при этом простой. Алгоритм Бойера-Мура близок к КМП по сложности и для определенного круга задач (где образец не содержит повторяющихся фрагментов) он быстрее. Но зато для другого круга задач (где образец и строка поиска содержат повторяющиеся последовательности, как в примерах к статье) он заметно уступает КМП. Наконец, есть задачи, где выбор того или другого — дело вкуса (о которых не спорят). В некоторых случаях (или даже областях) алгоритм Ахо — Корасик может оказаться эффективней и КМП и Бойер-Мура. Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо.

Дополнение по результатам обсуждения

Можно модифицировать префикс-функцию, чтобы она использовала буфер не О(длина строки+длина образца) а О(длина образца). В этом случае память нужно выделить только для хранения длин префиксов образца, а длины префиксов строки поиска не запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), префикс-функция вызывает функцию обработки найденного фрагмента. Модифированная функция prefix_find добавлена в статью. Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кому-то может понадобиться.На возможность сэкономить память обратил мое внимание mayorovp и он же дал ссылку в своем сообщении на реализацию варианта префикс-функции, которая выводит позиции найденных фрагментов в cout. По замечанию staticlab изменил тип переменных на size_t (так действительно будет корректнее).Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях:
Иллюстрации
Строки нулей и единиц одинаковы, только в первых двух иллюстрациях индексы с 0, а в следующих — с 1. На самом деле, это не принципально, поскольку в массив пишутся длины подстрок, а способ нумерации символов в строке роли не играет.Последняя иллюстрация — взгляд «с высоты птичьего полета» на префиксы-суффиксы строкиhabrhabhabrhabrhabrhabhabrhabhabrhabhabrhabrhabrhabhabrhabraбез массивов индексов и длин.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 57

    +2

    Я не понимаю, почему в таблице в разделе "Переходим к трюку" на позиции 6 (там где '@') стоит 3, а на позиции 8 стоит 5 как будто там найдено совпадение. Нет ли там ошибки?

      +2
      Спасибо за замечание — это проблемы копипаста. Так канительно создавать таблицы. Особенно с цветным выделением, т.к. оно сильно отвлекает внимание. Вроде сейчас поправил.
      +9
      Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.

      Я вас огорчу. Вокруг таких реальных задач вся биоинформатика крутиться. Там масса алгоритмов разработано именно для анализа строк ДНК.
        +1
        Вы меня не огорчили — я в курсе. Это популярная статья для программистов, которым просто нужен быстрый поиск. Процитирую себя: «Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо».Специалисты по ДНК (или по поиску вирусных сигнатур) относятся именно к тем, на кого это статься не ориентирована.
        Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
          +3
          присоединюсь ZlodeiBaal, лучше кроме «олимпиадного програмирования» там в статье привести еще какие-то примеры, когда такие вещи нужны на самом деле
          +1
          Позволю добавить, КМП примечателен отсутствием сдвига указателя чтения «назад», тем самым позволяя просматривать поток данных.
          Префикс-функция, о которой велась речь в статье, выстраивает конечный автомат, по которому движется алгоритм при поиске подстроки. Это позволяет переложить такой алгоритм на ASIC/FPGA и сферу применения — intrusion detection systems, где данных много, да еще и хранить их для дальнейшего анализа не всегда возможно.
          +3
          В результате расчет значений массива занимает время порядка О(длина строки).

          А где доказательство?


          А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.

          Почему задача, которую он решает, названа "вроде как совсем другой", если это прямое обобщение исходной задачи?


          Для нахождения образца ааbаа в строке ааbааbааааbааbаааb склеим образец со строкой вот так ааbаа@ааbааbааааbааbаааb и вызовем для нее префикс-функцию для заполнения массива.

          … и сразу же повысим требования по памяти в несколько раз! Дополнительной памяти правильная реализация алгоритма требует O(N), где N — длина образца. Ваш же способ требует O(N+M) дополнительной памяти, где N — длина образца, M — длина текста.

            –3
            Даже не заню, что Вам ответить: наверное эта статья не для Вас. Раз требования к памяти возрастают в несколько раз, то Ваши образцы в несколько раз больше строки, где они ищутся.
              0
              К сожалению, я неправильно понял Ваше замечание, а редактироване заблокировано. Можете дать ссылку, где памяти требуется O(N)?.. Во всех задачах на acmp, timus (где я использовал КМП) проблем ни с памятью ни со скоростью не было. Но все же интересно.
                0

                Там, вероятно, и вовсе нет задач где можно так запросто упереться в ограничения, особенно при работе с текстом. Но привычка совершать лишние действия может тяжело аукнуться при попытке решения какого-нибудь "гроба".

                  0
                  Так все-таки есть ссылка на O(N) или нет?
                    +2

                    Я, наверное, вас не так понял. Вам ссылку на задачу надо или на алгоритм? Если второе — то вот: https://ideone.com/qmNQ39

                      0
                      Спасибо, завтра поизучаю.
                      • UFO just landed and posted this here
                          0
                          Я понял (а точнее, даже вспомнил). В случае, когда надо найти не все вхождения подстроки, а первое вхождение, память нужно выделить для хранения длин префиксов образца. А длины суффиксов строки поиска на запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), функция прекращает работу и возвращает найденную позицию.
                            0
                            Нет никакой разницы нужно ли найти первое вхождение или же все вхождения. Код, предложенный вам выше, ищет все вхождения (роль @ в нем играет '\0' на конце образца)
                              0
                              Код выводит информацию об нахождении в cout. Получается, что он «заточен» под определенную задачу. С массивом проще — вызывающая прощедура сама решает, что делась с найдеными фрагментами и делает. Хотя можно модифицировать префикс-функцию так, чтобы ее передавала функция, обрабатывающая найденный фрагмент.

                              Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
                                +1
                                Возвращайте вектор позиций вхождения или вы считаете, что функция поиска подстроки должна возвращать в качестве ответа массив вычисленных префикс-функций?
                                  0

                                  В чем проблема вместо вывода в cout делать что-то еще?


                                  Или вы имеете в виду, что в данной реализации алгоритма не хватает выделения самого алгоритма? Тогда можно сделать вот так: https://ideone.com/zn9Fe4


                                  Или вот так: https://ideone.com/pnafkx


                                  Или еще кучей других способов. Алгоритм от этого не изменится, это лишь оформление.

                                    0
                                    Я дополнил статью процедурой, которая использует память О(длина образца).
                                  • UFO just landed and posted this here
                                      0
                                      На домашнем компьютере 200+ Гиг в память не затянешь, по-любому придется считывать порциями. Будет порция 20-50-100Мб особой роли не играет. 30 Гиг я читал сам и работал с программами воосстановления файлов на разделах под терабайт. Они тоже читают порциями, правда неясно, какой алгоритм используют.
                                      Ну а если встретится задачка, где будут жесткие ограничения по памяти и скорости — так я добавил в статью процедуру prefix_find, которой нужен буфер только под образец.
                    0
                    В результате расчет значений массива занимает время порядка О(длина строки).

                    В худшем случае это S = sum(ln k, 1, n) и это не линейное время так как предел lim S/n видимо бесконечный.
                      +2

                      Э… там вообще-то и в худшем случае линейное время, просто автор поста не стал это доказывать.


                      Мы не можем уменьшать текущий префикс большее число раз, чем увеличивали. А увеличиваем мы его только на 1 и не чаще 1 раз на символ из текста и шаблона. Отсюда и оценка времени O(N+M)

                        0
                        Точно, мы ж не до конца каждый раз спускаемся, просчитался, спасибо за уточнение.
                    +1
                    А почему тогда не алгоритм Бойера-Мура, который настолько же сложно объясняется, но часто работает быстрее в несколько раз? (до N раз быстрее, где N — длина образца — хотя иногда, надо признать, может работать и медленнее, чем КМП — худшая оценка у него выше)
                    (Если первый символ в КМП не совпадает, мы всегда смещаемся на единицу, если последний символ в БМ не совпадает, и этого символа нет в образце — мы смещаемся сразу на длину образца! И даже если есть одинаковые символы, мы почти всегда смещаемся больше, чем на единицу).
                      +7
                      Написал бы про Байера-Мура — обязательно кто-то спросил бы «прочему не КМП — он ведь такой-разтакой»? Я захотел написать про КМП и написал. Вам нравится Баейр- Мур — так напишите! Зачем противопоставлять одно другому? Чем больше интересных/полезных статей — тем лучше.
                        +1
                        Ок. Но я был бы признателен, если бы вы хотя бы упомянули его в вашей статье рядом с алгоритмом Ахо-Карасик.
                          0
                          Ну, если только упомянуть — так я внес дополнение. Вы удовлетворены? Все же это статья про алгоритм КМП, а не монография про различные методы эффективного поиска.
                            +1
                            Спасибо большое. Я просто считаю, что всегда, описывая определённое решение, нужно указать область применимости, недостатки алгоритма и альтернативные решения.
                            Кстати, теперь я понимаю, почему вы не любите алгоритм Бойера-Мура — вы не считаете, что он существенно быстрее в большинстве случаев :) А, между тем, в grep используется именно Бойер-Мур, и именно из-за его более высокой скорости.
                            Объяснение ваше в посте про БМ некорректное. БМ тем медленнее, чем больше частичных совпадений между концом образца и текстом, а не внутри образца. Но его можно улучшить, чтобы этого замедления не было, и тогда худшая оценка будет совпадать к КМП. Получится как с быстрой сортировкой против сортировки вставками.
                            Поскольку редко кто в 2016м году подобные алгоритмы программирует сам вручную, я бы не рекомендовал на практике КМП, а рекомендовал БМ или Ахо-Карасика.
                            А для знакомства с алгоритмами рекомендовал бы Кормана вместо Хабрахабра :)
                              +2

                              Кхм, вообще-то алгоритм Ахо-Карасика решает другую задачу, его с КМП и БМ сравнимать некорректно.

                                0
                                Правильно, алгоритм Ахо-Корасика решает расширенную задачу, когда шаблонов много, но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика, и заодно немного сэкономить на группировке шаблонов в готовый trie.
                                  0

                                  Вообще-то, алгоритм Ахо-Корасика — это и есть КМП, расширенный на насколько образцов :)

                                    0
                                    Хм, покажите, где я утверждаю обратное :)
                                      +1
                                      но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика

                                      Нельзя взять алгоритм Ахо-Корасика вместо раширенного на несколько образцов КМП — потому что это один и тот же алгоритм.

                                        0
                                        В любой библиотеке это будут разные методы, потому что в КМП нет тривиальной части алгоритма, объединяющей образцы в единый конечный автомат.
                                        В https://habrahabr.ru/post/198682/ вообще даже утверждают, что КМП — совсем другая задача))
                                          0

                                          https://ideone.com/zn9Fe4


                                          Метод next преобразовать в функцию, задающую КА, довольно легко.

                                –1
                                Я пользовалсся Бойер-Муром, но при решении одной из задач все время выскакивал TL. В обсуждениях я прочитал, что надо использовать КМП (в строке поиска и в образце были часто повторяющиеся фрагменты и Б-М не мог быстро «скакать», как я понял из обсуждения). Почитал про КМП, запрограммировал и задача прошла «на ура», а сам КМП запал в душу. Это было давненько, с тех пор я стал использовать его и больше никогда TL не встречался (по причине медленного поиска). Наверное потому, что олимпиадные задачи не требуют чего-то более серьезного.
                                  +1

                                  Потому что, как я уже писал ранее, использовать БМ без турбосдвига нельзя.

                                    –1
                                    Для олимпиадных целей (цель — написать как можно проще, лишь бы попадало в требуемую асимптотику) самый простой алгоритм — это поиск с помощью хеш-функции. Особенно когда нам нужно найти только первое вхождение, тогда нам не обязательно верить, что если хеш-функции двух строк равны, то эти строки совпадают.
                                      0

                                      КМП проще хеш-функции

                                        0
                                        С использованием хешей не самый простой, и не самый быстрый, особенно при поиске одного шаблона. Вот когда шаблонов много — тогда стоит подумать об алгоритме Рабина-Карпа, например.
                                          0
                                          Да, я именно про Рабина-Карпа и говорил (забыл, что у него есть устоявшееся название). А почему не самый простой то? По объему кода сопоставим с КМП, зато идея, лежащая в его основе, гораздо проще. И при этом довольный мощный: обобщается для двумерного случая (найти за O(n*m) все вхождения заданного шаблона прямоугольника в квадратной матрице n*m), для случая множества шаблонов.
                                            +1
                                            Я вам что-то сначала поверил, а теперь осознал, что не понимаю, как он обобщается на случай множества шаблонов нефиксированной длины.
                                          0
                                          Понятное дело, для олимпиад специально придумают контрпримеры, чтобы использовать алгоритм O(MN) вместо O(M+N) было нельзя. Наиболее простой контрпример — шаблон и строка из одинаковых букв («ааааа» и «аааааааааааааааа»). Нужна модификация БМ с турбосдвигом, которая работает за 2*N в худшем случае, хотя, конечно, она сложнее.
                                          Но подумайте вот о чём. Олимпиады — это лишь тренировка навыков скоростного программирования, а не практика написания программных продуктов.
                                          Для написания реальных программных продуктов нельзя использовать те же самые критерии, что и для олимпиад.
                                          Поэтому лучше брать готовые алгоритмы, упакованные в библиотеки. Конечно, крайне желательно понимать, как они работают, чтобы знать их ограничения. Спасибо вам за хорошо иллюстрированный пост, я уверен, он поможет многим разобраться, что происходит. Но лучше думайте о промышленных программистах, которые будут использовать ваш пост, как руководство к действию — а нам всем потом именно их программами придётся пользоваться…
                                            0

                                            Библиотеки тоже кто-то пишет.

                                          +1
                                          Насчет grep не знаю, а вот что используют программы типа WinHex, работающие с разделами, восстановлением файлов, когда надо прокачать десятки (а то и сотни) гигабайт данных — интересно.
                                    +2

                                    Зато КМП легко расширяется для нескольких образцов — а алгоритм Бойера-Мура нет.


                                    Да и сложность в худшем случае может сыграть злую шутку, поэтому без эвристики турбосдвига алгоритм Бойера-Мура лучше не использовать. А с этой эвристикой алгоритм становится намного сложнее КМП.

                                    +1

                                    Почему в примере на С++ тип переменной длины и индексов size_t, а в примере на С — int?

                                      0
                                      Согласен, внес изменение.
                                      +1
                                      Кому интересно ещё почитать о КМП, то вот пару полезных ссылок:
                                      e-maxx
                                      Algolist
                                      Wikibooks

                                      Кстати, есть реализация КМП в Boost.Algorithm:
                                      GitHub
                                        0
                                        А объясните неучу как формируется массив длин префиксов?
                                          0
                                          В статье про это есть, правда без доказательств и оценки асимптотики. Если очень вкратце, то пусть 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 (для этого необходимо и достаточно, чтобы символ, следующий за концом соответствующего префикса, был с).

                                          Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
                                          0
                                          Случайно нет ли опечатки в «M[8]+1=5 b»?
                                            0
                                            Спасибо, есть такая опечатка. Надо же, никто до сих пор не заметил. Поправил на M[8]+1=6
                                            –1
                                            Напишите, как изменить размер шрифта для одного абзаца.
                                            Или как изменить шрифт внутри < source > Спасибо.
                                              –1
                                              Хотел дополнить статью таблицами, объясняющими КМП «на пальцах», но раз с ходу минусуют, значит не надо.

                                              Only users with full accounts can post comments. Log in, please.