Алгоритм Кнута - Морриса - Пратта Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=x[1]x[2]... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]... l[n], где l[i]=длина слова l(x[1]...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно являющегося его концом. Какое отношение все это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B? Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. Описать алгоритм заполнения таблицы l[1]...l[n]. Решение. Предположим, что первые i значений l[1]...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1]. Другими словами, нас интересуют начала Z слова x[1]...x[i+1, одновременно являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова Z' приписыванием буквы x[i+1] . Слово Z' является началом и концом слова x[1]...x[i]. Однако не любое слово, являющееся началом и концом слова x[1]...x[i], годится - надо, чтобы за ним следовала буква x[i+1]. Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x[1]...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное. Приписав в его конец х[i+1], получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела. Вот что получается: i:=1; 1[1]:=0; {таблица l[1]..l[i] заполнена правильно} while i <> n do begin len:= l[i] {len - длина начала слова x[1]..x[i], которое является его концом; все более длинные начала оказались неподходящими} while (x[len+1]<>х[i+1]) and (len>0) do begin {начало не подходит, применяем к нему функцию l} len:=l[len]; end; {нашли подходящее или убедились в отсутствии} if x[len+1]=x[i+1] do begin {х[1]..x[len] - самое длинное подходящее начало} l[i+1]:=len+1; end else begin {подходящих нет} l[i+1]:= 0; end; i:=i+1; end; Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C. Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием. Более точно, можно записать неравенство l[i+1]n) and (j<>m) do begin while (x[len+1]<>у[j+1]) and (len>0) do begin {начало не подходит, применяем к нему функцию l} len: = l[len]; end; {нашли подходящее или убедились в отсутствии} if x[len+1]=y[j+1] do begin {x[1]..x[len] - самое длинное подходящее начало} len:=len+1; end else begin {подходящих нет} len:=0; end; j:=j+1; end; {если len=n, слово X встретилось; иначе мы дошли до конца слова Y, так и не встретив X} Алгоритм Бойера - Мура Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.) Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x[1]...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему). Как заполнить массив pos? Решение. положить все pos[s] равными 0 for i:=1 to n do begin pos[x[i]]:=i; end; В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается. last:=n; {все предыдущие положения образца уже проверены} while last<= m do begin {слово не кончилось} if x[m]<>y[last] then begin {последние буквы разные} last:=last+(n-pos[y[last]]); {n - pos[y[last]] - это минимальный сдвиг образца, при котором напротив y[last] встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца} end else begin если нынешнее положение подходит, т.е. если x[i]..х[n]=y[last-n+1]..y[last], то сообщить о совпадении; last:=last+1; end; end; Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку last:=last+i заменить на last:=last+(n-u), где u - координата второго справа вхождения буквы x[n] в образец. Как проще всего учесть это в программе Решение. При построении таблицы pos написать for i:=1 to n-1 do... (далее как раньше), а в основной программе вместо last:=last+1 написать last:=last+n-pos[y[last]]; Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта. Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить. Решение. Пусть образец имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий. Алгоритм Рабина Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. Привести пример удобной для вычисления функции. Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться.) Привести пример семейства удобных функций. Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку.