Алгоритм поиска подстроки кнута морриса прата

Содержание

Алгоритм поиска по строке Кнута-Морриса-Пратта

Само задание таково:
Программа должна быть грамотно функционально разбита на модули и функции.
• Входные данные – текстовый файл.
• Выходные данные – текстовый файл, содержащий найденные слова с указанием позиции во входном файле (номер строки, позиция в строке, количество вхождений слова в файле).
номер строки: 3 позиция в строке:9

но при компилировании выдает ошибку

06.09.2012, 18:15

Поиск заданной подстроки в строке (алгоритм Кнута-Морриса-Пратта)
Привет всем. Мне нужно написать программу поиска заданной подстроки в строке. Если подстрока есть -.

Алгоритм Кнута, Морриса и Пратта
//описание функции алгоритма Кнута, Морриса и Пратта int KMPSearch(char *string, char *substring)<.

Алгоритм Кнута-Морриса-Пратта
Здравствуйте. Есть задание в котором необходимо найти вхождения подстроки в строку.Пример входных и.

Алгоритм Кнута-Морриса-Пратта
здравствуйте. можете объяснить по примеру алгоритм кнута-морриса-пратта

Алгоритм КМП(Кнута-Морриса-Пратта )
нужно с помощью алгоритма КМП найти первое вхождение одной числовой последовательности в другую .

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

пятница, 19 апреля 2013 г.

Алгоритм Кнута-Морриса-Пратта (КМП)

Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

Он относится к «правильным» подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.

Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Для понимания: Префикс строки A[ ..i ] — это строка из i первых символов строки A . Суффикс строки A[ j.. ] — это строка из | A |-j+1 последних символов. Подстроку из A будем обозначать как A[ i..j ] , а A[ i ] — i-ый символ строки.

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: «AAAAB», где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.

Для реализации данного алгоритма, нам необходимо рассмотреть, так называемую, префикс функцию.

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

Вот пример для «ababcaba»:

суффикс префикс p
a a
ab ab
ab a aba 1
ab ab abab 2
ababc ababc
ababc a ababca 1
ababc ab ababcab 2
ababc aba ababcaba 3

Итак, идея ясна? Ну тогда попробум написать префикс функцию в лоб:

Вроде работает, но как то много сравнений и проходов. Попробуем оптимизировать.
Начать можно с замены строки j = i, на j = d[i-1]+1.

Что нам это дает? А то, что незачем просматривать каждый раз с конца и до начала. Можно заметить, что если мы на предыдущем шаге (i-1) нашли вхождение > 0 (d[i-1]), то и начинать стоит с данной позиции (d[i-1]).

При i=4 ABAAB -> 2, тогда на i+1, т.е. i=5 смотрим не с j=i(5), а с 3! Т.к. либо счетчик вырастет и станет 3 в случае ABAABA, либо сбросится в 0 при любой другой букве.
И хотя мы делаем меньше сравнений(пропускаем середину слова), однако весь совпадающий префикс мы проходим, что не есть хорошо.

Это уже не плохо, однако, мы с Вами так и не научились использовать информацию, полученную на предыдущих итерациях.

Зная длину совпадения префикса с суффиксом по предыдущей букве, мы можем начать поиск сразу с этой позиции (d[j-1]) и продвигаясь вперед либо увеличивать данное значение (суффикс равный префиксу продолжит свой рост), либо обнуляется (нет совпадения).

В статье на хабре, вы можете ознакомиться с так называемой z-функцией.
Идея её очень схожа с префикс функцией, поэтому её реализацию я опущу :)

Итак, префикс функция готова, осталось применить её и решить поставленную задачу.

Вот такая идея описывается в книге Вирта, зная значения префикс ф-ии сдвигаться на заданное расстояние, однако кто-то мог заметить, что для решения задачи, нам достаточно было использовать только префикс функцию. Для этого достаточно сделать конкатенацию искомой подстроки, со строкой, через разделитель, заведомо уникальный(что-то вроде #) и применив префикс ф-ию. Если она даст значение равное длине искомой подстроки, значит мы нашли это место иначе — нет.

Надеюсь, идея понятна.
Мы рассмотрели с Вами один из «правильных» алгоритмов поиска подстроки, однако, классикой данной задачи стал алгоритм Бойера — Мура.
Автор статьи на Хабре утверждает, что он достаточно не тривиален и запутан, однако вынужден с ним не согласиться, что и покажу в следующей заметке.

Алгоритм Кнута-Морриса-Пратта

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

В алгоритме КМП строится не КА, а похожая на него машина распознавания, которая может делать несколько последовательных переходов из текущего состояния при анализе очередного символа текста.

Рассмотрим пример распознавания подстроки (выделены совпадающие символы текста и , текущее состояние , анализируемый символ – красный):

, но , поэтому машина не может перейти в , а должна перейти в новое состояние (т.е. сдвинется вправо относительно ). Используя уже проверенную , перейдем в наибольшее возможное состояние , для к-го , и сравним и :

, повторяем попытку для макс-ного , :

: переходим в сост-е , символ проверен.

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

При этом , т.е. является максимальным по длине префиксом , который совпадает с суффиксом . Отсюда следует, что очередное состояние определяется только подстрокой и никак не зависит от проверяемого текста .

Для поиска нужного состояния при распознавании подстроки-образца заранее вычисляется целочисленная префикс-функция (функция отказов):

Таблица значений для подстроки :

Машина распознавания подстроки :

Последовательность состояний при анализе строк:

При анализе очередного символа возможен возврат через несколько состояний.

Если текущее состояние , то можно сделать переходов в предыдущие состояния.

Но если машина распознавания находится в состоянии , должно выполняться условие .

При анализе символов было сделано ровно переходов в последующие состояния (по одному переходу на каждый символ, без переходов в предыдущие).

На каждый проверяемый символ текста приходится в среднем переходов.

Вычисление префикс-функции для подстроки :

F[q] = (P[q] == P[k+1])? k+1 : 0;

В цикле while можно сделать максимум шаг, но это возможно, если до этого был выполнен шаг цикла for, на которых цикл while вообще не выполнялся.

Общая трудоемкость данного алгоритма составляет .

Поиск всех вхождений подстроки в строку после вычисления префикс-функции :

найдено_вхождение(i–m); q = F[q];

Рассуждая по аналогии с алгоритмом вычисления , можно сделать вывод, что трудоемкость данного алгоритма .

Общая трудоемкость алгоритма КМП составляет и не зависит от количества символов в алфавите.

Вариант алгоритма Бойера-Мура с вычислением функций стоп-символа и безопасного суффикса (Кормен).

Алгоритм Рабина-Карпа

При поиске подстроки в строке необходимо найти все допустимые сдвиги, т.е. такие значения , , для которых .

Основная идея алгоритма:

— преобразовать подстроку и сравниваемую с ней часть текста в целые числа, заданные цифрами в системе счисления с основанием (обозначим эти числа, соответственно, и );

— сравнивать не и , а и (одно сравнение чисел вместо сравнений символов);

— обеспечить быстрое вычисление числа , соответствущего сдвигу , преобразованием значения .

Сдвиг является допустимым, если .

Для вычисления не требуется знание строки . Используя схему Горнера, можно получить за время :

Также за можно вычислить :

Значения и связаны рекуррентным соотношением:

Если заранее получить константу (за время ), то будет вычисляться по известному за ЭШ, а проверку всего текста можно провести за .

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

Для преодоления этой трудности нужно перейти к модульной арифметике: вместо сверхдлинных целых чисел использовать их остатки от деления по некоторому модулю .

Если задано некоторое целое , то любое произвольное целое можно единственным образом представить в виде:

, где ( — частное, — остаток).

Для любых целых выполняется равенство:

т.е. операцию деления по модулю можно вносить в скобки и применять к отдельным значениям.

Чтобы исключить переполнение для целых в алгоритме Рабина-Карпа необходимо выбрать такое (простое), чтобы значение помещалось в машинное слово, и при расчете , , и постоянно вычислять остатки по :

вместо использовать ; при вычислении брать остаток после каждого умножения текущего числа на ,

Приведенные выше оценки трудоемкостей сохранятся, но теперь все вычисления проводятся с короткими числами, и каждая арифметическая операция будет одним ЭШ.

Пример вычисления для строки из десятичных цифр ( , , Кормен и др.):

14152 = (31415 — 3∙10000) ∙10 + 2 – для длинных целых.

= ((31415 mod 13 – (3∙10000) mod 13) ∙10 + 2) mod 13 =

= ((7 – 9) ∙10 + 2) mod 13 = 8 – для остатков.

Правильное вычисление r = a mod q (при q > 0):

Алгоритм поиска подстроки кнута морриса прата

По мотивам лекции Сагунова Данила и реализации indy256

Алгоритм относится к разряду алгоритмов поиска подстроки в строке.

Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S : П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].

Пусть S = “abababaaabababac”
z[0] = П(“a”) = 0
z[1] = П(“ab”) = 0
z[2] = П(“aba”) = 1
z[3] = П(“abab”) = 2
z[4] = П(“ababa”) = 3
z[5] = П(“ababab”) = 4
z[6] = П(“abababa”) = 5
z[7] = П(“abababaa”) = 1
z[8] = П(“abababaaa”) = 1
z[9] = П(“abababaaab”) = 2
z[10] = П(“abababaaaba”) = 3
z[11] = П(“abababaaabab”) = 4
z[12] = П(“abababaaababa”) = 5
z[13] = П(“abababaaababab”) = 6
z[14] = П(“abababaaabababa”) = 7
z[15] = П(“abababaaabababac”) = 0

Можно заметить, что z-функция может увеличиваться за один шаг не более чем на 1, а уменьшиться на произвольное количество.

Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.

Илон Маск рекомендует:  orphans в CSS

Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”ababa b a a
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa) = 3
3) Сравниваем 3-ый символ с последним: “aba b aba a ”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “a b ababa a ”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “ a bababa a ”. Успех =)
Значит z[7] = 1.

Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.

Понятно, что в данной реализации происходит лишнее выделение памяти, и не всегда есть возможность вести себя так вальяжно.

Более эффективная реализация:

Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.

Алгоритм Кнута-Морриса-Пратта

Простейший алгоритм

Суть метода, о котором пойдет речь ниже, заключается в следующем: мы проверяем, совпадают ли m символов текста (начиная с выбранного) с символами нашей строки, пытаясь примерить шаблон куда только возможно. Естественно, реализовать описанный алгоритм проще всего (код на языке Pascal):

Var T : array[1..40000] of char;

S : array[1..10000] of char;

for i:=1 to n-m+1 do

for i:=1 to m-1 do

for i:=m+1 to n+1 do

writeln(‘Образец входит в текст начиная с ‘,i-m,’-ого символа’);

for i:=1 to m-1 do

for i:=m+1 to n+1 do

while (j 0) and (S[k+1]<>S[i]) do

Теперь разберемся, почему же данная процедура вычисляет префикс-функцию правильно. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k] 0) and (S[k+1]<>T[i]) do

writeln(‘Образец входит в текст начиная с ‘,i-m+1,’-ого символа’);

Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

Напоследок хочу заметить, что простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считают, сколько символов совпало в процессе работы. И еще: алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее. Так что делайте выводы.

P.S.Все программы проверены на работоспособность, достаточно вставить соответствующие сегменты кода вместо многоточий.

Описание алгоритмов сортировки, часть 1
Описание алгоритмов сортировки, часть 2
Алгоритмы поиска данных

Автор: Владимир Ткачук — mycоmр.cоm.uа

| следующая лекция ==>
Выявление тенденции развития изучаемого явления (тренда) по данным о выпуске продукции по месяцам за 6-ой год методами скользящей средней и аналитического выравнивания. | Алексанова И.Н. — «Сущности среди нас». Тайны невидимого мира

Дата добавления: 2020-12-05 ; просмотров: 1099 | Нарушение авторских прав

Алгоритм поиска Кнута Морриса

Нужно было сделать поиск фразы в книге и возвратить кол-во совпадений и время поиска. Все алгоритмы кроме Кнута получились. Алгоритм Кнута тоже получился,но преподаватель говорит, что он медленно работает. Вот функция:

И использую её так:

Я пробовал также без цикла делать, считать совпадения внутри knuth_morris. Время почти не отличилось. Что не так с алгоритмом? Подскажите пожалуйста.

1 ответ 1

В общем разобрался. Во-первых, в моём алгоритме вычисляется префикс функция лишние разы, поэтому нужно делать без цикла. Много скорости не прибавит, если маленький текст и большая поисковая строка. Но когда много исходного текста, алгоритм Кнута обходит наивный алгоритм во много раз.
Итак, вот исправленная функция:

И её использование:

Всё ещё ищете ответ? Посмотрите другие вопросы с метками c алгоритм или задайте свой вопрос.

Похожие

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2020 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2020.11.12.35403

Алгоритм Кнута, Морриса и Пратта

Рассмотрим сначала более простой случай. Пусть все символы строки-образца S различны. Начнем сравнивать символы S слева направо с первыми m символами строки A. Допустим, что несравнение символов произошло в позиции k £ m, т.е. первые k–1 букв A и S совпали. С какой позиции A следует начать новое сравнение с S? Поскольку символ ak–1 = sk–1, то ak–1 не может совпасть с предыдущими символами S (потому что все символы S различны). Значит, перед продолжением сравнения строк можно сдвинуть S так, чтобы ее первый символ сравнивался сразу с k-м символом A (т.е. с той позицией A, где было обнаружено несовпадение).

Если в S есть совпадающие символы, рассчитать величину сдвига несколько сложнее.

Определим dj как длину наибольшей подстроки из S, которая заканчивается в позиции j и совпадает с началом строки S во всех позициях, кроме последней. Это можно подробно расписать таким образом:

Если такой подстроки не существует, то положим dj = 0. Тогда нетрудно показать, что, если первое несовпадение при сравнении символов из A и S произошло на паре символов ai ¹ sj, то перед продолжением сравнения следует заменить индекс j на dj, а значение индекса i не изменять (т.е. надо сдвинуть строку S на j – dj позиций вдоль строки A). Действительно, поскольку символы a[i – dj + 1], a[i – d j + 2], … ,
a[i – 1] успешно сравнились с символами s[j – dj + 1], s[j – d j + 2], … , s[j – 1], то они, согласно (7.1), должны сравниться и с символами s[1], s[2], … , s[dj – 1], а потому сравнение можно продолжать с пары символов a[i] и s[dj].

Если же значение j стало равно 0, то надо увеличить i и j на единицу, т.е. начать сопоставление символов заново с позиции i + 1 в строке A и с первой позиции в строке S.

Ниже приведены примеры значений dj, рассчитанных для различных строк-образцов.

1) a a a a a a 2) q w e r t y u i
0 0 0 0 0 0 0 1 1 1 1 1 1 1
3) a a b a a b c 4) a b c d a c e f a b d f
0 0 2 0 0 2 4 0 1 1 1 0 2 1 1 0 1 3 1
5) a b b a b b a c 6) a b a b a b a c a b c
0 1 1 0 1 1 0 5 0 1 0 1 0 1 0 6 0 1 3

Рассмотрим работу алгоритма на примере, показанном на рис. 7.1. В строке A = ‘aabaabaaabaabc’ ищется подстрока S = ‘aabaabc’ (см. выше, пример 3).

1 2 3 4 5 6 7 8 9 10 11 12 13 14
A: a a b a a b a a a b a a b c
Шаг 1: a a b a a b c
Шаг 2: a a b a a b c
Шаг 3: a a b a a b c

Рис. 7.1. Пример работы алгоритма Кнута, Морриса и Пратта

На первом шаге обнаруживается несовпадение букв ai и sj при i = 7 и j = 7. Выполняется присваивание j := 4. Сравнение продолжается, пока при i = 9 и j = 6 не происходит очередное несовпадение. Делается присваивание j := 2. На сей раз сравнение проходит успешно.

Отдельный вопрос – как лучше всего рассчитывать величины dj. В алгоритме на этот вопрос дается довольно неожиданный ответ. Задачу расчета dj для всех значений j можно рассматривать как модифицированную задачу поиска, в которой роль строки поиска играет S, а роль строки-образца – начальная часть той же строки. Поэтому вычисление dj выполняется примерно по тому же алгоритму, что и сам поиск вхождения S в A.

Ниже приведен текст функции, реализующей алгоритм поиска КМП.

function KMPSearch(A: StringN; S: StringM): Integer;

Кнут-Морриса-Пратта алгоритм — Knuth–Morris–Pratt algorithm

В информатике , то Кнута-Морриса-Пратта строк поиска алгоритм (или KMP алгоритм ) ищет вхождения «слово» W в главном «текстовая строка» S , используя наблюдение , что , когда происходит рассогласование, само слово воплощает в себе достаточно информации чтобы определить , где на следующий матч может начаться, таким образом , минуя повторное рассмотрение ранее подобранных символов.

Алгоритм был задуман в 1970 году Дональд Кнут и Vaughan Pratt , и независимо друг от друга Джеймс Х. Моррис . Это был первый линейный алгоритм времени для согласования строки. Три опубликовал его совместно в 1977. Самостоятельно, в 1969 году, Матиясевич обнаружил подобный алгоритм, закодированный двумерный машиной Тьюринга, в то время как изучение строк соответствия шаблона задачи распознавания.

содержание

Алгоритм сравнения строк хочет найти начальный индекс m в строке , S[] которая соответствует слово для поиска W[] .

Самый простой алгоритм , чтобы искать совпадение символов при последовательных значениях индекса m , положение в строке ищется, то есть S[m] . Если индекс m достигает конца строки , то нет никакого совпадения в этом случае поиск называется «глючить». В каждой позиции m алгоритм сначала проверяет равенство первого символа в слове разыскивается, то есть S[m] =? W[0] . Если совпадение найдено, алгоритм проверяет другие символы в словах , которое ищется путем проверки последовательных значений индекса позиции слова, i . Алгоритм возвращает символ W[i] в слове проводится поиск и проверка на равенство выражения S[m+i] =? W[i] . Если все последующие символы соответствуют в W на позиции m , то совпадение найдено на этой позиции в строке поиска.

Как правило, проверка процесса будет быстро отклонить матч суда. Если строки равномерно распределенные случайные буквы, то вероятность того, что матч персонажей 1 в 26. В большинстве случаев проверка процесс будет отклонить матч на первой букве. Вероятность того, что первые две буквы будут соответствовать 1 в 26 2 (1 в 676). Так что если символы являются случайными, то ожидаемая сложность поиска строки S[] длины к это порядка K сравнений или O ( K ). Ожидаемая производительность очень хорошо. Если S[] 1 миллион символов и W[] 1000 символов, то строка поиск должен завершить примерно через 1,04 миллиона сравнений символов.

Это ожидаемое исполнение не гарантируется. Если строки не являются случайными, то проверка суда m может занять много сравнений символов. В худшем случае , если две строки совпадают во всем , кроме последней буквы. Представьте себе , что строка S[] состоит из 1 миллиона символов, которые все , и что слово 999 A символов , заканчивающиеся в конечном B характер. Простой алгоритм сравнения строк Рассмотрим теперь 1000 символов на каждой позиции пробной до отказа матча и продвижения позиции суда. Простой пример строки поиска теперь будет принимать около 1000 символов сравнения раз 1 миллиона позиций на 1 млрд сравнений символов. Если длина является п , то производительность в худшем случае это O ( Kп ). W[] W[]

Алгоритм KMP имеет лучшую производительность в худшем случае , чем простой алгоритм. KMP тратит немного времени Предвычисления таблицы (по порядку величины W[] , O ( п )), а затем использует эту таблицу , чтобы сделать эффективный поиск строки в O ( к ).

Разница заключается в том, что KMP использует предыдущую информацию соответствия , что простой алгоритм не делает. В приведенном выше примере, когда KMP видит матч испытание на неудачу 1000 символа ( i = 999) , потому что S[m+999] ≠ W[999] она будет увеличиваться m на 1, но он будет знать , что первые 998 символов в новой позиции уже совпадают. КМР соответствует 999 A символов прежде , чем обнаружить несоответствие в 1000 — символе (позиция 999). Выросшая позиция матча пробной m один выбрасывает первый A , так что KMP знает , что есть 998 A символов , которые соответствуют W[] и не Retest их; то есть, KMP наборы i для 998. KMP сохраняет свои знания в предвычисленной таблице и два переменных. Когда KMP обнаруживает несоответствие, таблица определяет , сколько KMP увеличится (переменный m ) и где он возобновит тестирование (переменный i ).

алгоритм KMP

Пример алгоритма поиска

Для того, чтобы проиллюстрировать детали , выполняемых алгоритмом, рассмотрим (относительно искусственного) пробег алгоритма, где W = «ABCDABD» и S = «ABC ABCDAB ABCDABCDABDE». В любой данный момент времени, алгоритм находится в состоянии определяется двумя целыми числами:

  • m , Обозначающее положение в S котором для проспективного матча W начинается,
  • i , Обозначая индекс рассматриваемого в данный момент персонажа W .
Илон Маск рекомендует:  Выбор цвета

На каждом шаге алгоритм сравнивает S[m+i] с W[i] и приращения , i если они равны. Это изображено, в начале работы, как

Алгоритм сравнивает последовательные символы W с «параллельными» персонажами S , переходя от одного к другому приращению , i если они совпадают. Однако, на четвертом этапе S[3] = ‘ ‘ не соответствует W[3] = ‘D’ . Вместо того , начиная искать снова S[1] , мы отмечаем , что не ‘A’ происходит между положениями 1 и 2 в S ; поэтому, проверив все эти символы ранее (и зная , что они соответствуют соответствующим символам W ), нет никаких шансов найти начало матча. Поэтому множества алгоритмов m = 3 и i = 0 .

Это совпадение не в начальный символ, так что наборы алгоритмов m = 4 и i = 0

Здесь i не увеличивает счет почти полного матча , «ABCDAB» пока i = 6 давать несоответствие в W[6] и S[10] . Однако, незадолго до конца текущего частичного совпадения, было то , что подстрока , «AB» которая может стать началом нового матча, поэтому алгоритм должен принять это во внимание. Поскольку эти символы соответствуют два символа до текущей позиции, то эти символы не должны быть проверены еще раз; множества алгоритмов m = 8 (начало исходного префикса) и i = 2 (сигнализации первые два символа совпадают) и продолжает соответствие. Таким образом, алгоритм не только опускает сопоставлен символы S (The «AB» ), но и ранее соответствие символов W (префикс «AB» ).

Этот поиск в новой позиции не удается сразу , потому что W[2] (а ‘C’ ) не соответствует S[10] (а ‘ ‘ ). Как и в первом испытании, несоответствие вызывает алгоритм , чтобы вернуться к началу W и начинает поиск несогласованной позиции символа S : m = 10 сброс i = 0 .

Матч на m=10 не удается сразу, поэтому алгоритм следующий пытается m = 11 и i = 0 .

Опять же, алгоритм матчи «ABCDAB» , но следующий символ, ‘C’ , не совпадает с последним символом ‘D’ слова W . Рассуждая , как и раньше, наборы алгоритмов m = 15 , чтобы начать на строку из двух символов , «AB» ведущих к текущему положению, установить i = 2 , и продолжить соответствие с текущей позиции.

На этот раз матч будет завершен, и первый герой матча S[15] .

Описание псевдокод для алгоритма поиска

Приведенный выше пример содержит все элементы алгоритма. На данный момент, мы предполагаем существование таблицы «частичное соответствие» T , описанный ниже , который указывает , где мы должны искать для начала нового матча в том случае, если текущий один заканчивается в рассогласования. Записи о T построены так , что если у нас есть совпадение , начиная с , S[m] что не удается при сравнении S[m + i] с W[i] , то следующим возможным матч начнется в индексе m + i — T[i] в S (то есть, T[i] это сумма «откат» мы должны сделать после того, как рассогласования). Это имеет два последствия: во- первых, T[0] = -1 , что указывает на то, что если W[0] это несоответствие, мы не можем вернуться назад и должен просто проверить следующий символ; и второй, хотя на следующий возможный матч начнется в индексе m + i — T[i] , как и в приведенном выше примере, мы не должны фактически проверить любой из T[i] символов после этого, так что мы продолжаем поиск с W[T[i]] . Ниже приведен пример псевдокода реализация алгоритма поиска KMP.

Эффективность алгоритма поиска

Если предположить , что предварительное существование таблицы T , поиск часть алгоритма Кнута-Морриса-Пратта имеет сложность O ( п ) , где п есть длина S и вывода является большой-O обозначения . Для постоянных накладных , понесенных при входе и выходе из функции Кроме этого , все вычисления выполняются в while цикле. Для того, чтобы ограничивать количество итераций этого цикла; Замечу , что T построено таким образом , что если матч , который начался на S[m] сбой при сравнении S[m + i] с W[i] , то следующим возможным матч должен начаться в S[m + (i — T[i])] . В частности, следующий возможно совпадение должно происходить на более высоком , чем индекс m , так что T[i] .

Этот факт предполагает , что цикл может выполняться не более 2 п раз, так как на каждой итерации он выполняет один из двух ветвей в петле. Первая ветвь неизменно увеличивается i и не изменяется m , так что индекс m + i в настоящее время всматривался характер S увеличивается. Вторая ветвь добавляет i — T[i] к m , и , как мы уже видели, это всегда положительное число. Таким образом, место m начала текущего потенциального матча увеличивается. В то же время, вторая ветвь уходит m + i без изменений, для m получает i — T[i] к нему добавляется, и сразу же после того, как T[i] получает назначение в качестве нового значения i , следовательно new_m + new_i = old_m + old_i — T[old_i] + T[old_i] = old_m + old_i . Теперь, цикл завершается , если m + i = п ; Таким образом, каждая ветвь петли может быть достигнута на наиболее п раз, так как они , соответственно увеличивают либо m + i или m , и m ≤ m + i : если m = п , то , конечно , m + i ≥ п , так , что , так как это увеличивает с шагом единицами, самым большим, мы должны были иметь m + i = п в какой — то момент в прошлом, и поэтому в любом случае мы бы сделали.

Таким образом, цикл выполняется не более 2 п раз, показывая , что временная сложность алгоритма поиска является О ( п ).

Вот еще один способ думать о время выполнения: Допустим , мы начинаем соответствовать W и S в положении i и p . Если W существует в виде подстроки в S точке р, то W[0..m] = S[p..p+m] . В случае успеха, то есть, слово и текст , совпадающий по позициям ( W[i] = S[p+i] ), мы увеличиваем i на 1. В случае отказа, то есть, слово и текст не совпадают в позициях ( W[i] ≠ S[p+i] ), текст указатель хранится до сих пор, в то время как указатель слова откатывается определенное количество ( i = T[i] где T это таблица прыжка), и мы пытаемся соответствовать W[T[i]] с S[p+i] . Максимальное количество переклички задней части i ограниченно i , то есть, для любого отказа, мы можем только откат, насколько мы продвинулись до отказа. Тогда ясно , что время автономной работы 2 п .

«Частичное совпадение» таблица (также известные как «функция отказа»)

Цель таблицы , чтобы алгоритм не соответствует любому символу из S более чем один раз. Ключевое наблюдение о природе линейного поиска , что позволяет этому случиться, что в проверив некоторый отрезок основной строки против начального сегмента рисунка, мы точно знаем , на котором размещают новый потенциальный матч мог продолжать ток позиция может начаться до текущей позиции. Другими словами, мы «до поиска» сам шаблон и составить список всех возможных позиций резервными , которые обходят максимум безнадежных персонажей, не жертвуя любые потенциальные матчи в этом.

Мы хотим , чтобы иметь возможность смотреть вверх, для каждой позиции W , длина самого длинного возможного начального сегмента W ведущих (но не включая) эту позицию, кроме полного сегмента , начиная с , W[0] что просто не в состоянии соответствовать; это то , как далеко мы должны вернуться назад в поисках очередной матч. Следовательно , T[i] именно длина самого длинного возможного надлежащего начального сегмента , W который также является сегмент подстроки , заканчивающейся на W[i — 1] . Мы используем соглашение , что пустая строка имеет длину 0. Так как рассогласования в самом начале картины является частным случаем (нет возможности отката), мы установили T[0] = -1 , как описано ниже .

Практический пример алгоритма табличного строительства

Рассмотрим пример W = «ABCDABD» первой. Мы увидим , что она вытекает много по той же схеме, что и основной поиск, а также является эффективным по тем же причинам. Мы устанавливаем T[0] = -1 . Для того, чтобы найти T[1] , мы должны обнаружить надлежащий суффикс из «A» которых также является префикс шаблона W . Но нет соответствующих суффиксов «A» , поэтому мы устанавливаем T[1] = 0 . Для того, чтобы найти T[2] , мы видим , что подстрока W[0] — W[1] ( «AB» ) имеет собственный суффикс «B» . Однако «Б» не является префиксом шаблона W . Таким образом, мы устанавливаем T[2] = 0 .

Продолжая T[3] , мы сначала проверить правильность суффикс длины 1, как и в предыдущем случае она не сможет . Должны ли мы также проверить более длинные суффиксы? Нет, мы теперь , что есть ярлык для проверки всех суффиксов: давайте скажем , что мы открыли собственный суффикс , который является собственным префиксом (Надлежащая префикс строки не равна самой строки) и заканчивая W[2] длиной 2 (максимально возможный); то его первый символ также является собственным префиксом W , следовательно , правильного самого префикса, и она заканчивается W[1] , которую мы уже определили не произошло , как T[2] = 0 и не T[2] = 1 . Поэтому на каждом этапе, правило ярлыка является то , что необходимо рассмотреть проверки суффиксов данного размера т + 1 , только если действительный суффикс размера м был найден на предыдущем этапе (то есть T[x] = m ) и не должен беспокоить , чтобы проверить м + 2, т + 3 и т.д.

Поэтому нам не нужно даже касаются подстрок , имеющая длину 2, как и в предыдущем случае, подошва одна с длиной 1 терпит неудачу, так T[3] = 0 .

Переходим к последующему W[4] , ‘A’ . Та же логика показывает , что самая длинная подстрока нам нужно рассмотреть имеет длину 1, как и в предыдущем случае , он не так «D» не является префиксом W . Но вместо того , чтобы настройки T[4] = 0 , мы можем сделать лучше, отметив , что W[4] = W[0] , а также о том , что Двойник из T[4] предполагает соответствующий S характер, S[m+4] было несоответствие и поэтому S[m+4] ≠ ‘A’ . Таким образом , нет никакого смысла в перезапуске поиска на S[m+4] ; мы должны начать 1 вперед. Это означает , что мы можем сдвинуть образец W по длине матча плюс один символ, так T[4] = -1 .

Рассмотрим теперь следующий символ, W[5] , что ‘B’ : хотя осмотром самой длинной подстроки , казалось бы ‘A’ , мы еще множество T[5] = 0 . Рассуждения аналогичны , почему T[4] = -1 . W[5] Сам проходит матч префикс , начатый с W[4] , и можно считать , что соответствующий символ в S , S[m+5] ≠ ‘B’ . Так возвратов прежде , чем W[5] бессмысленно, но S[m+5] может быть ‘A’ , следовательно T[5] = 0 .

Наконец, мы видим , что следующий символ в текущей стартовый отрезок на W[4] = ‘A’ бы ‘B’ , да и это тоже W[5] . Кроме того, тот же аргумент , как и выше , показывает , что нам не нужно искать , прежде чем W[4] найти сегмент для W[6] , так что это, и мы принимаем T[6] = 2 .

Таким образом, мы составляем следующую таблицу:

i 1 2 3 4 5 6 7
W[i] В С D В D
T[i] -1 -1 2
i 1 2 3 4 5 6 7 8 9
W[i] В С В В С
T[i] -1 -1 1 -1 -1 3 2

Другой пример (слегка изменен из предыдущего примера):

i 1 2 3 4 5 6 7 8 9
W[i] В С В В
T[i] -1 -1 1 -1 -1 3 -1 3

Еще более сложный пример:

i 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
W[i] п р T я С я п T Е я N п р С ЧАС U T Е
T[i] -1 -1 2 -1 3

Описание псевдокода для алгоритма табличного строительства

Приведенный выше пример иллюстрирует общую методику для сборки стола с минимумом суеты. Принцип заключается в том, что из общего поиска: большая часть работы уже была сделана в получении текущей позиции, поэтому очень мало должно быть сделано в уходящем его. Лишь незначительная сложность заключается в том, что логика, которая является правильной в конце строки ошибочно дает без надлежащих подстрок в начале. Это требует некоторого кода инициализации.

Эффективность алгоритма табличного строительства

Сложность алгоритма этой таблицы O(k) , где k длина W . Что касается некоторой инициализации всей работы делается в , кроме while петли, достаточно , чтобы показать , что этот цикл выполняется в O(k) момент, который будет сделан путем одновременного изучения количества pos и pos — cnd . В первом отделении, pos — cnd сохраняется, так как оба pos и cnd увеличиваются одновременно, но , естественно, pos увеличивается. Во втором отделении, cnd заменяется T[cnd] , что мы видели выше , всегда строго меньше cnd , увеличивая таким образом pos — cnd . Так pos ≥ pos — cnd , это означает , что на каждой стадии либо pos или нижняя граница для pos увеличения; Поэтому , так как алгоритм завершается один раз pos = k , он должен прекратить после того, как в большинстве 2k итераций цикла, так как pos — cnd начинается 1 . Таким образом, сложность алгоритма этой таблицы O(k) .

Илон Маск рекомендует:  Что такое код farheapfillfree

Эффективность алгоритма KMP

Так как эти две части алгоритма имеют, соответственно, сложности O(k) и O(n) сложность общего алгоритма O(n + k) .

Эти сложности не являются одинаковыми, независимо от того , сколько повторяющихся узоров в W или S .

Варианты

В режиме реального времени версия KMP может быть реализована с помощью отдельной функции сбоя таблицы для каждого символа в алфавите. Если несоответствие происходит по характеру в тексте, функция сбоя таблица для символа консультируются для индекса в шаблоне , на котором имело место несоответствие. Это возвращает длину самой длинной подстроки , заканчивающуюся на соответствие префикса шаблона, с дополнительным условием , что символ после префикса является . С этим ограничением, символ в тексте не нужно еще раз проверить на следующем этапе, и поэтому только постоянное число операций выполняются между обработкой каждого индекса текста. Это удовлетворяет в режиме реального времени ограничение вычислений. Икс <\ Displaystyle х>Икс <\ Displaystyle х>я <\ Displaystyle я>я <\ Displaystyle я>Икс <\ Displaystyle х>Икс

Алгоритм Бут использует модифицированную версию функции предварительной обработки KMP , чтобы найти лексикографически минимальное вращение строки . Функция отказа постепенно вычисляется как строка поворачивается.

Алгоритм Кнута, Морриса и Пратта

Читайте также:

  1. Алгоритм
  2. АЛГОРИТМ
  3. Алгоритм Бойера и Мура
  4. Алгоритм быстрого преобразования Фурье (БПФ)
  5. Алгоритм быстрого преобразования Фурье.
  6. Алгоритм вивчення сім’ї
  7. Алгоритм відповіді на рецепт, який виписаний на супозиторії методом викачування
  8. Алгоритм действий как структурный элемент социально-педагогической технологии.
  9. Алгоритм действия кэш-памяти
  10. Алгоритм деления пополам.
  11. Алгоритм и программа

Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они совместно опубликовали в 1977 году. Алгоритм Кнута, Морриса и Пратта (КМП-алгоритм) является алгоритмом, который фактически требуюет только сравнений даже в самом худшем случае. Рассматриваемый алгоритм основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки фактически известна пройденная часть строки и можно, вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке.

Основным отличием алгоритма Кнута, Морриса и Пратта от алгоритма прямого поиска заключается в том, что сдвиг подстроки выполняется не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Следовательно, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим (рис. 2). На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом.

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

i i i i
Строка A B C A B C A A B C A B D
Подстрока A B C A A B B D C A A B B A D C B A C B A D B D

Рис.2. Демонстрация алгоритма Кнута, Морриса и Пратта

//описание функции алгоритма Кнута, Морриса и Пратта

int KMPSearch(char *string, char *substring)<

Алгоритм Кнута — Морриса — Пратта (стр. 1 из 2)

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово

и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел 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 слова

одновременно являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова 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 из предыдущего раздела.

Вот что получается:

while i <> n do begin

его концом; все более длинные начала оказались

while (x[len+1]<>х[i+1]) and (len>0) do begin

if x[len+1]=x[i+1] do begin

Доказать, что число действий в приведенном только что алгоритме не превосходит 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

if x[len+1]=y[j+1] do begin

слова 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

В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается.

while last y[last] then begin

при котором напротив y[last] встанет такая же

буква в образце. Если такой буквы нет вообще,

то сдвигаем на всю длину образца>

если нынешнее положение подходит, т.е. если

то сообщить о совпадении;

Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s],

т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку

где u — координата второго справа вхождения буквы x[n] в образец.

Как проще всего учесть это в программе

Решение. При построении таблицы pos написать

for i:=1 to n-1 do.

(далее как раньше), а в основной программе вместо

Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.

Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить.

Решение. Пусть образец имеет вид baaa. aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент.

Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий.

Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.

В чем выигрыш при таком подходе. Казалось бы, ничего — ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция.

Привести пример удобной для вычисления функции.

Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.)

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL