algorithm
Подстрочный поиск
Поиск…
Алгоритм KMP в C
Учитывая текст TXT и шаблон погладить, цель этой программы будет печатать все вхождение Пата в TXT.
Примеры:
Входные данные :
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
выход:
Pattern found at index 10
Входные данные :
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
выход:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C Язык:
// C program for implementation of KMP pattern searching
// algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // length of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
Выход:
Found pattern at index 10
Ссылка:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Введение в алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа - это алгоритм поиска строк, созданный Ричардом М. Карпом и Майклом О. Рабином, который использует хэширование, чтобы найти какой-либо из набора строк шаблонов в тексте.
Подстрокой строки является другая строка, которая встречается в. Например, ver является подстрокой stackoverflow . Не следует путать с подпоследовательностью, потому что обложка является подпоследовательностью одной и той же строки. Другими словами, любое подмножество последовательных букв в строке является подстрокой данной строки.
В алгоритме Рабина-Карпа мы создадим хэш нашего шаблона, который мы ищем, и проверьте, соответствует ли скользящий хэш нашего текста шаблону или нет. Если это не соответствует, мы можем гарантировать, что шаблон не существует в тексте . Однако, если он соответствует, шаблон может присутствовать в тексте . Давайте посмотрим на пример:
Допустим, у нас есть текст: yeminsajid, и мы хотим узнать, существует ли в тексте шаблон nsa . Чтобы вычислить хеш-хэш и хэш-лист, нам нужно использовать простое число. Это может быть любое простое число. Для этого примера возьмем prime = 11 . Мы определим хэш-значение, используя эту формулу:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Мы будем обозначать:
a -> 1 g -> 7 m -> 13 s -> 19 y -> 25
b -> 2 h -> 8 n -> 14 t -> 20 z -> 26
c -> 3 i -> 9 o -> 15 u -> 21
d -> 4 j -> 10 p -> 16 v -> 22
e -> 5 k -> 11 q -> 17 w -> 23
f -> 6 l -> 12 r -> 18 x -> 24
Хэш-значение nsa будет:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Теперь мы находим скользящий хэш нашего текста. Если скользящий хеш совпадает с хэш-значением нашего шаблона, мы проверим соответствие строк или нет. Поскольку наш шаблон имеет 3 буквы, мы возьмем 1-й 3 буквы yem из нашего текста и вычислим значение хэша. Мы получаем:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Это значение не совпадает с хэш-значением нашего шаблона. Поэтому строка здесь не существует. Теперь нам нужно рассмотреть следующий шаг. Чтобы вычислить хэш-значение нашей следующей строки emi . Мы можем вычислить это, используя нашу формулу. Но это было бы довольно тривиально и стоило бы нам больше. Вместо этого мы используем другую технику.
- Мы вычитаем значение Первого письма предыдущей строки из нашего текущего значения хэш-функции. В этом случае y . Получаем,
1653 - 25 = 1628. - Мы разделим разницу на наше простое , что для этого примера равно 11 . Получаем,
1628 / 11 = 148. - Добавим новую букву X (простое) ᵐ⁻¹ , где m - длина шаблона, с частным, что равно i = 9 . Получаем,
148 + 9 X 11² = 1237.
Новое значение хэша не равно нашему хэш-значению паттерна. Двигаясь дальше, для n получаем:
Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806
Это не соответствует. После этого для s получаем:
Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462
Это не соответствует. Далее, для a получаем:
Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344
Это матч! Теперь мы сравниваем наш шаблон с текущей строкой. Поскольку обе строки совпадают, подстрока существует в этой строке. И мы возвращаем исходную позицию нашей подстроки.
Псевдокод будет:
Расчет хеширования:
Procedure Calculate-Hash(String, Prime, x):
hash := 0 // Here x denotes the length to be considered
for m from 1 to x // to find the hash value
hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash
Пересчет хешей:
Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash
Строковое совпадение:
Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
if Text[i] is not equal to Pattern[i]
Return false
end if
end for
Return true
Рабина-Карпа:
Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
Return i
end if
CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1
Если алгоритм не находит никакого совпадения, он просто возвращает -1 .
Этот алгоритм используется при обнаружении плагиата. Учитывая исходный материал, алгоритм может быстро искать бумагу для экземпляров предложений из исходного материала, игнорируя такие данные, как случай и пунктуация. Из-за обилия искомых строк однолинейные поисковые алгоритмы здесь нецелесообразны. Опять же, алгоритм Кнута-Морриса-Пратта или алгоритм поиска по методу Boyer-Moore - это алгоритм поиска алгоритма с одним шаблоном, чем Rabin-Karp . Тем не менее, это алгоритм выбора для множественного поиска по шаблону. Если мы хотим найти любое из большого числа, скажем k, шаблонов фиксированной длины в тексте, мы можем создать простой вариант алгоритма Рабина-Карпа.
Для текста длины n и p- образных изображений с комбинированной длиной m его среднее время и наилучшее время пробега O (n + m) в пространстве O (p) , но в худшем случае это O (nm) .
Введение в алгоритм Кнут-Моррис-Пратт (КМП)
Предположим, что у нас есть текст и шаблон . Нам нужно определить, существует ли шаблон в тексте или нет. Например:
+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Index | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+
Этот шаблон существует в тексте . Поэтому наш поиск подстроки должен вернуть 3 , индекс позиции, с которой начинается этот шаблон . Итак, как работает наша процедура поиска подстроки грубой силы?
Обычно мы делаем это: мы начинаем с 0-го индекса текста и 0-го индекса нашего * шаблона, и мы сравниваем Text [0] с Pattern [0] . Поскольку они не соответствуют, мы переходим к следующему индексу нашего текста, и мы сравниваем текст [1] с Pattern [0] . Поскольку это совпадение, мы увеличиваем индекс нашего шаблона и индекс текста . Мы сравниваем текст [2] с рисунком [1] . Они также подходят. Следуя той же самой процедуре, описанной ранее, мы теперь сравниваем текст [3] с рисунком [2] . Поскольку они не совпадают, мы начинаем со следующей позиции, где мы начали находить матч. Это индекс 2 текста . Мы сравниваем текст [2] с рисунком [0] . Они не совпадают. Затем увеличивая индекс текста , мы сравниваем Text [3] с Pattern [0] . Они совпадают. Снова текст [4] и Pattern [1] соответствуют, текст [5] и шаблон [2] соответствуют, а текст [6] и шаблон [3] соответствуют. Поскольку мы достигли конца нашего шаблона , мы теперь возвращаем индекс, с которого начинался наш матч, т. Е. 3 . Если наш шаблон был: bcgll , это означает, что если шаблон не существует в нашем тексте , наш поиск должен возвращать исключение или -1 или любое другое предопределенное значение. Мы можем ясно видеть, что в худшем случае этот алгоритм займет время O(mn) где m - длина текста, а n - длина шаблона . Как мы сокращаем эту сложность во времени? Именно здесь на картинке появляется алгоритм поиска подстроки KMP.
Алгоритм поиска Knuth-Morris-Pratt String или алгоритм KMP ищет появление «шаблона» в основном «тексте», используя наблюдение, что, когда происходит несоответствие, само слово содержит достаточную информацию, чтобы определить, где может начаться следующий матч , тем самым минуя повторное рассмотрение ранее согласованных символов. Алгоритм был задуман в 1970 году Донульдом Кнутом и Воганом Праттом и независимо от Джеймса Морриса . Трио опубликовало его совместно в 1977 году.
Давайте расширим наш пример Text и Pattern для лучшего понимания:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+
Сначала наш текст и шаблон соответствуют индексу 2 . Текст [3] и шаблон [3] не совпадают. Поэтому наша цель - не возвращаться назад в этом тексте , то есть в случае несоответствия мы не хотим, чтобы наше совпадение начиналось с позиции, с которой мы начали сопоставляться. Для этого мы будем искать суффикс в нашем шаблоне прямо перед нашим несоответствием (подстрока abc ), который также является префиксом подстроки нашего шаблона . В нашем примере, поскольку все символы уникальны, суффиксов нет, это префикс нашей подобранной подстроки. Итак, что это значит, наше следующее сравнение начнется с индекса 0 . Подождите немного, вы поймете, почему мы это сделали. Затем мы сравниваем Text [3] с Pattern [0], и это не соответствует. После этого для текста из индекса 4 в индекс 9 и для шаблона от индекса 0 до индекса 5 мы найдем совпадение. Мы находим несоответствие в Text [10] и Pattern [6] . Поэтому мы берем подстроку из шаблона прямо до точки, где происходит несоответствие (подстрока abcdabc ), мы проверяем суффикс, который также является префиксом этой подстроки. Мы можем видеть, что ab является суффиксом и префиксом этой подстроки. Это означает, что, поскольку мы сопоставлены до Text [10] , символы перед ошибкой являются ab . Из этого можно сделать вывод, что поскольку ab также является префиксом подстроки, которую мы взяли, нам не нужно снова проверять ab, и следующая проверка может начинаться с Text [10] и Pattern [2] . Нам не пришлось оглядываться на весь текст , мы можем начать прямо с того места, где произошло наше несоответствие. Теперь мы проверяем Text [10] и Pattern [2] , так как это несоответствие, а подстрока перед несоответствием ( abc ) не содержит суффикса, который также является префиксом, мы проверяем Text [10] и Pattern [0] , они не совпадают. После этого для текста из индекса 11 в индекс 17 и для шаблона из индекса 0 в индекс 6 . Мы находим несоответствие в Text [18] и Pattern [7] . Таким образом, мы снова проверяем подстроку перед несоответствием (substring abcdabc ), а find abc - как суффикс, так и префикс. Поэтому, поскольку мы сопоставлялись с Pattern [7] , abc должен быть до Text [18] . Это означает, что нам не нужно сравнивать до тех пор, пока текст [17] и наше сравнение не начнутся с текста [18] и шаблона [3] . Таким образом, мы найдем матч, и мы вернем 15, что является нашим начальным индексом матча. Так наш поиск подстроки KMP работает с использованием суффикса и префикса.
Теперь, как мы можем эффективно вычислить, является ли суффикс таким же, как префикс, и в какой момент начать проверку, существует ли несоответствие символа между Text и Pattern . Давайте рассмотрим пример:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Мы будем генерировать массив, содержащий требуемую информацию. Назовем массив S. Размер массива будет таким же, как длина рисунка. Поскольку первая буква шаблона не может быть суффиксом какого-либо префикса, мы поместим S [0] = 0 . Сначала возьмем i = 1 и j = 0 . На каждом шаге мы сравниваем Pattern [i] и Pattern [j] и приращение i . Если есть совпадение, мы помещаем S [i] = j + 1 и приращение j , если есть несоответствие, мы проверяем предыдущую позицию значения j (если доступно) и устанавливаем j = S [j-1] (если j не равен 0 ), мы продолжаем делать это до тех пор, пока S [j] не будет соответствовать S [i] или j не станет 0 . Для более позднего мы положим S [i] = 0 . Для нашего примера:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Шаблон [j] и Pattern [i] не совпадают, поэтому мы увеличиваем i, а так как j равно 0 , мы не проверяем предыдущее значение и ставим Pattern [i] = 0 . Если мы будем продолжать увеличивать i , то для i = 4 мы получим соответствие, поэтому поместим S [i] = S [4] = j + 1 = 0 + 1 = 1 и приращение j и i . Наш массив будет выглядеть так:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | | | |
+---------+---+---+---+---+---+---+---+---+
Так как Pattern [1] и Pattern [5] являются совпадением, мы помещаем S [i] = S [5] = j + 1 = 1 + 1 = 2 . Если продолжить, мы найдем несоответствие для j = 3 и i = 7 . Так как j не равно 0 , положим j = S [j-1] . И мы сравним символы в i и j, такие же или нет, поскольку они одинаковы, мы поместим S [i] = j + 1. Наш завершенный массив будет выглядеть так:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Это наш необходимый массив. Здесь ненулевое значение S [i] означает, что существует суффикс длины S [i], такой же, как префикс в этой подстроке (подстрока от 0 до i ), а следующее сравнение начнется с S [i] + 1 позиции Образец . Наш алгоритм генерации массива будет выглядеть так:
Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
if Pattern[i] is equal to Pattern[j]
S[i] := j + 1
j := j + 1
i := i + 1
else
if j is not equal to 0
j := S[j-1]
else
S[i] := 0
i := i + 1
end if
end if
end while
Сложность времени для создания этого массива - O(n) а сложность пространства также O(n) . Чтобы убедиться, что вы полностью поняли алгоритм, попробуйте создать массив для шаблона aabaabaa и проверить, соответствует ли результат этому .
Теперь давайте проведем поиск подстроки, используя следующий пример:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Text | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+
У нас есть текст , шаблон и предварительно вычисленный массив S, используя нашу логику, определенную ранее. Мы сравниваем Text [0] и Pattern [0], и они одинаковы. Текст [1] и шаблон [1] совпадают. Текст [2] и шаблон [2] не совпадают. Мы проверяем значение в позиции прямо перед несоответствием. Так как S [1] равно 0 , то суффикса не будет такого же, как префикс в нашей подстроке, и наше сравнение начинается в позиции S [1] , которая равна 0 . Итак, Pattern [0] не такой, как Text [2] , поэтому мы движемся дальше. Текст [3] совпадает с шаблоном [0], и существует совпадение с текстом [8] и паттерном [5] . Мы делаем один шаг назад в массиве S и находим 2 . Таким образом, это означает, что существует префикс длины 2, который также является суффиксом этой подстроки ( abcab), которая является ab . Это также означает, что есть текст ab перед текстом [8] . Поэтому мы можем смело игнорировать Pattern [0] и Pattern [1] и начать наше следующее сравнение с Pattern [2] и Text [8] . Если мы продолжим, мы найдем шаблон в тексте . Наша процедура будет выглядеть так:
Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
if Pattern[j] is equal to Text[i]
j := j + 1
i := i + 1
if j is equal to n
Return (j-i)
else if i < m and Pattern[j] is not equal t Text[i]
if j is not equal to 0
j = S[j-1]
else
i := i + 1
end if
end if
end while
Return -1
Сложность времени этого алгоритма, кроме вычисления суффиксного массива, равна O(m) . Поскольку GenerateSuffixArray принимает O(n) , общая временная сложность алгоритма KMP: O(m+n) .
PS: Если вы хотите найти несколько экземпляров Pattern в тексте , вместо того, чтобы возвращать значение, распечатайте его / сохраните и установите j := S[j-1] . Также сохраните flag чтобы отслеживать, находили ли вы какое-либо событие или нет и обрабатываете его соответствующим образом.
Python Реализация алгоритма KMP.
Haystack : строка, в которой данный шаблон нужно искать.
Игла : шаблон для поиска.
Сложность времени : часть поиска (метод strstr) имеет сложность O (n), где n - длина стога сена, но поскольку игла также предварительно анализируется для таблицы префикса здания O (m), требуется для построения таблицы префикса, где m - длина игла.
Поэтому общая временная сложность для KMP равна O (n + m)
Сложность пространства : O (m) из-за таблицы префиксов на игле.
Примечание. После выполнения возвращается исходная позиция совпадения в стоге сена (если есть совпадение) else возвращает -1, для краевых случаев, например, если игла / стог сена - пустая строка или игла не найдена в стоге сена.
def get_prefix_table(needle):
prefix_set = set()
n = len(needle)
prefix_table = [0]*n
delimeter = 1
while(delimeter<n):
prefix_set.add(needle[:delimeter])
j = 1
while(j<delimeter+1):
if needle[j:delimeter+1] in prefix_set:
prefix_table[delimeter] = delimeter - j + 1
break
j += 1
delimeter += 1
return prefix_table
def strstr(haystack, needle):
# m: denoting the position within S where the prospective match for W begins
# i: denoting the index of the currently considered character in W.
haystack_len = len(haystack)
needle_len = len(needle)
if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
return -1
prefix_table = get_prefix_table(needle)
m = i = 0
while((i<needle_len) and (m<haystack_len)):
if haystack[m] == needle[i]:
i += 1
m += 1
else:
if i != 0:
i = prefix_table[i-1]
else:
m += 1
if i==needle_len and haystack[m-1] == needle[i-1]:
return m - needle_len
else:
return -1
if __name__ == '__main__':
needle = 'abcaby'
haystack = 'abxabcabcaby'
print strstr(haystack, needle)