Дано текст txt[0 . . . N-1] і візерунок ліжко[0 . . . M-1] , напишіть функцію search(char pat[], char txt[]), яка друкує всі входження pat[] у txt[]. Ви можете це припустити Н > М .
приклади:
Рекомендована проблема Вирішити проблемувведення: txt[] = ЦЕ ТЕСТОВИЙ ТЕКСТ, pat[] = ТЕСТ
Вихід: Шаблон знайдено під індексом 10введення: txt[] = ВАШІ БАТЬКИ
pat[] = AABA
Вихід: Шаблон знайдено за індексом 0, шаблон знайдено за індексом 9, шаблон знайдено за індексом 12Надходження візерунка в тексті
Ми обговорювали наивний алгоритм пошуку шаблонів у попередній пост . Найгірший випадок складності алгоритму Naive становить O(m(n-m+1)). Часова складність алгоритму KMP становить O(n+m) у найгіршому випадку.
KMP (Knuth Morris Pratt) Пошук шаблонів:
The Наївний алгоритм пошуку шаблонів не працює добре у випадках, коли ми бачимо багато відповідних символів, за якими йде невідповідний символ.
приклади:
1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (не найгірший випадок, але поганий випадок для Naive)
Алгоритм зіставлення KMP використовує властивість виродження (шаблон, що має однакові підшаблони, що з’являються в шаблоні більше одного разу) шаблону та покращує складність найгіршого випадку до O(n+m) .
Основна ідея алгоритму KMP така: щоразу, коли ми виявляємо невідповідність (після деяких збігів), ми вже знаємо деякі символи в тексті наступного вікна. Ми використовуємо цю інформацію, щоб уникнути зіставлення символів, які, як ми знаємо, все одно збігатимуться.
Огляд відповідності
txt = AAAAABAAABA
pat = AAAA
Порівнюємо перше вікно txt з так самоtxt = АААА БАТЬКО
навіть = АААА [Початкова позиція]
Знаходимо збіг. Це те саме, що Наївне зіставлення рядків .На наступному кроці ми порівнюємо наступне вікно txt з так само .
txt = ААААА ЗНИЩИТИ
навіть = АААА [Візерунок зміщено на одну позицію]Тут KMP виконує оптимізацію над Naive. У цьому другому вікні ми порівнюємо лише четвертий A шаблону
з четвертим символом поточного вікна тексту, щоб вирішити, чи збігається поточне вікно чи ні. Оскільки ми знаємо
перші три символи все одно збігатимуться, ми пропустили збіг перших трьох символів.Потрібна попередня обробка?
З наведеного вище пояснення виникає важливе питання, як дізнатися, скільки символів потрібно пропустити. Щоб знати це,
ми попередньо обробляємо шаблон і готуємо цілочисельний масив lps[], який повідомляє нам кількість символів, які потрібно пропустити
Огляд попередньої обробки:
- Алгоритм KMP попередньо обробляє pat[] і створює допоміжний lps[] розміру м (так само, як розмір шаблону), який використовується для пропуску символів під час зіставлення.
- Ім'я lps вказує на найдовший належний префікс, який також є суфіксом. Правильний префікс — це префікс із забороненим цілим рядком. Наприклад, префікси ABC: , A, AB і ABC. Правильні префікси , A і AB. Суфікси рядка: , C, BC і ABC.
- Ми шукаємо lps у підпатернах. Більш чітко ми зосереджуємось на підрядках шаблонів, які є як префіксом, так і суфіксом.
- Для кожного підшаблону pat[0..i], де i = 0 до m-1, lps[i] зберігає довжину максимального відповідного префікса, який також є суфіксом підшаблону pat[0..i ].
lps[i] = найдовший правильний префікс pat[0..i], який також є суфіксом pat[0..i].
Примітка: lps[i] також можна визначити як найдовший префікс, який також є правильним суфіксом. Нам потрібно правильно використовувати його в одному місці, щоб переконатися, що весь підрядок не розглядається.
Приклади конструкції lps[]:
Для шаблону AAAA lps[] дорівнює [0, 1, 2, 3]
Для шаблону ABCDE lps[] дорівнює [0, 0, 0, 0, 0]
Для шаблону AABAACAABAA lps[] дорівнює [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
Для шаблону AAACAAAAAC lps[] дорівнює [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
Для шаблону AAABAAA lps[] дорівнює [0, 1, 2, 0, 1, 2, 3]
Алгоритм попередньої обробки:
У частині попередньої обробки
- Обчислюємо значення в lps[] . Для цього ми відстежуємо довжину найдовшого значення суфікса префікса (ми використовуємо тільки змінна для цієї мети) для попереднього індексу
- Ініціалізуємо lps[0] і тільки як 0.
- Якщо pat[len] і ліжка відповідність, ми збільшуємо тільки на 1 і призначити збільшене значення lps[i].
- Якщо pat[i] і pat[len] не збігаються і len не дорівнює 0, ми оновлюємо len до lps[len-1]
- Побачити computeLPSArray() у наведеному нижче коді для деталей
Ілюстрація попередньої обробки (або створення lps[]):
pat[] = ААААААА
=> len = 0, i = 0:
- lps[0] завжди дорівнює 0, ми переходимо до i = 1
=> len = 0, i = 1:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- збережіть його в lps[i] і виконайте i++.
- Встановіть len = 1, lps[1] = 1, i = 2
=> len = 1, i = 2:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- збережіть його в lps[i] і виконайте i++.
- Встановіть len = 2, lps[2] = 2, i = 3
=> len = 2, i = 3:
- Оскільки pat[len] і pat[i] не збігаються, а len> 0,
- Встановіть len = lps[len-1] = lps[1] = 1
=> len = 1, i = 3:
- Оскільки pat[len] і pat[i] не збігаються, а len> 0,
- len = lps[len-1] = lps[0] = 0
=> len = 0, i = 3:
заперечення дискретної математики
- Оскільки pat[len] і pat[i] не збігаються, а len = 0,
- Встановіть lps[3] = 0 і i = 4
=> len = 0, i = 4:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- Збережіть його в lps[i] і виконайте i++.
- Встановіть len = 1, lps[4] = 1, i = 5
=> len = 1, i = 5:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- Збережіть його в lps[i] і виконайте i++.
- Встановіть len = 2, lps[5] = 2, i = 6
=> len = 2, i = 6:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- Збережіть його в lps[i] і виконайте i++.
- len = 3, lps[6] = 3, i = 7
=> len = 3, i = 7:
- Оскільки pat[len] і pat[i] не збігаються, а len> 0,
- Встановіть len = lps[len-1] = lps[2] = 2
=> len = 2, i = 7:
- Оскільки pat[len] і pat[i] збігаються, виконайте len++,
- Збережіть його в lps[i] і виконайте i++.
- len = 3, lps[7] = 3, i = 8
Ми зупиняємось тут, оскільки ми побудували весь lps[].
Реалізація алгоритму KMP:
На відміну від Наївний алгоритм , де ми зсуваємо шаблон на один і порівнюємо всі символи під час кожного зсуву, ми використовуємо значення з lps[], щоб вирішити наступні символи, які потрібно зіставити. Ідея полягає в тому, щоб не збігатися з персонажем, який, як ми знаємо, все одно збігатиметься.
Як за допомогою lps[] визначити наступні позиції (або дізнатися кількість символів, які потрібно пропустити)?
- Порівняння pat[j] з j = 0 починаємо з символів поточного вікна тексту.
- Ми зберігаємо відповідні символи txt[i] і pat[j] і продовжуємо збільшувати i та j, тоді як pat[j] і txt[i] зберігають відповідність .
- Коли ми бачимо a невідповідність
- Ми знаємо, що символи pat[0..j-1] збігаються з txt[i-j…i-1] (зверніть увагу, що j починається з 0 і збільшує його лише за наявності збігу).
- Ми також знаємо (із наведеного вище визначення), що lps[j-1] — це кількість символів у pat[0…j-1], які є як належним префіксом, так і суфіксом.
- З наведених вище двох пунктів ми можемо зробити висновок, що нам не потрібно зіставляти ці символи lps[j-1] з txt[i-j…i-1], оскільки ми знаємо, що ці символи все одно збігатимуться. Щоб зрозуміти це, розглянемо наведений вище приклад.
Нижче наведено ілюстрацію описаного вище алгоритму:
Розглянемо txt[] = АААААААААААААААААААААААААААААААААА , pat[] = АААА
Тоді, якщо ми дотримуємося описаного вище процесу створення LPS lps[] = {0, 1, 2, 3}
-> i = 0, j = 0: txt[i] і pat[j] збігаються, виконайте i++, j++
-> i = 1, j = 1: txt[i] і pat[j] збігаються, виконайте i++, j++
-> i = 2, j = 2: txt[i] і pat[j] збігаються, виконайте i++, j++
-> i = 3, j = 3: txt[i] і pat[j] збігаються, виконайте i++, j++
-> i = 4, j = 4: Оскільки j = M, надрукувати знайдений шаблон і скинути j, j = lps[j-1] = lps[3] = 3
порівняти рядок javaТут, на відміну від Naive алгоритму, ми не зіставляємо перші три
персонажів цього вікна. Значення lps[j-1] (у вищевказаному кроці) дало нам індекс наступного символу для відповідності.-> i = 4, j = 3: txt[i] і pat[j] збігаються, виконайте i++, j++
-> i = 5, j = 4: Оскільки j == M, надрукувати знайдений шаблон і скинути j, j = lps[j-1] = lps[3] = 3
Знову ж таки, на відміну від Naive алгоритму, ми не зіставляємо перші три символи цього вікна. Значення lps[j-1] (у вищевказаному кроці) дало нам індекс наступного символу для відповідності.-> i = 5, j = 3: txt[i] і pat[j] НЕ збігаються, а j> 0, змініть лише j. j = lps[j-1] = lps[2] = 2
-> i = 5, j = 2: txt[i] і pat[j] НЕ збігаються, а j> 0, змініть лише j. j = lps[j-1] = lps[1] = 1
-> i = 5, j = 1: txt[i] і pat[j] НЕ збігаються, а j> 0, змініть лише j. j = lps[j-1] = lps[0] = 0
-> i = 5, j = 0: txt[i] і pat[j] НЕ збігаються, а j дорівнює 0, ми робимо i++.
-> i = 6, j = 0: txt[i] і pat[j] збігаються, виконайте i++ і j++
-> i = 7, j = 1: txt[i] і pat[j] збігаються, виконайте i++ і j++
Ми продовжуємо цей шлях, доки в тексті не буде достатньо символів для порівняння з символами в шаблоні...
Нижче наведено реалізацію вищезазначеного підходу:
C++
// C++ program for implementation of KMP pattern searching> // algorithm> #include> void> computeLPSArray(>char>* pat,>int> M,>int>* lps);> // Prints occurrences of pat[] in txt[]> 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[M];> >// Preprocess the pattern (calculate lps[] array)> >computeLPSArray(pat, M, lps);> >int> i = 0;>// index for txt[]> >int> j = 0;>// index for pat[]> >while> ((N - i)>= (M - j)) {> >if> (pat[j] == txt[i]) {> >j++;> >i++;> >}> >if> (j == M) {> >printf>(>'Found pattern at index %d '>, i - j);> >j = lps[j - 1];> >}> >// mismatch after j matches> >else> if> (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; } } } // Fills lps[] for given pattern pat[0..M-1] void computeLPSArray(char* pat, int M, int* lps) { // length of the previous longest prefix suffix int len = 0; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 int i = 1; while (i if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = 0; i++; } } } } // Driver code int main() { char txt[] = 'ABABDABACDABABCABAB'; char pat[] = 'ABABCABAB'; KMPSearch(pat, txt); return 0; }> |
>
>
Java
// JAVA program for implementation of KMP pattern> // searching algorithm> class> KMP_String_Matching {> >void> KMPSearch(String pat, String txt)> >{> >int> M = pat.length();> >int> N = txt.length();> >// create lps[] that will hold the longest> >// prefix suffix values for pattern> >int> lps[] =>new> 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> ((N - i)>= (M - j)) {> >if> (pat.charAt(j) == txt.charAt(i)) {> >j++;> >i++;> >}> >if> (j == M) {> >System.out.println(>'Found pattern '> >+>'at index '> + (i - j));> >j = lps[j ->1>];> >}> >// mismatch after j matches> >else> if> (i && pat.charAt(j) != txt.charAt(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; } } } void computeLPSArray(String pat, int M, int lps[]) { // length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = len; i++; } } } } // Driver code public static void main(String args[]) { String txt = 'ABABDABACDABABCABAB'; String pat = 'ABABCABAB'; new KMP_String_Matching().KMPSearch(pat, txt); } } // This code has been contributed by Amit Khandelwal.> |
>
>
Python3
# Python3 program for KMP Algorithm> def> KMPSearch(pat, txt):> >M>=> len>(pat)> >N>=> len>(txt)> ># create lps[] that will hold the longest prefix suffix> ># values for pattern> >lps>=> [>0>]>*>M> >j>=> 0> # index for pat[]> ># Preprocess the pattern (calculate lps[] array)> >computeLPSArray(pat, M, lps)> >i>=> 0> # index for txt[]> >while> (N>-> i)>>=> (M>-> j):> >if> pat[j]>=>=> txt[i]:> >i>+>=> 1> >j>+>=> 1> >if> j>=>=> M:> >print>(>'Found pattern at index '> +> str>(i>->j))> >j>=> lps[j>->1>]> ># mismatch after j matches> >elif> i and 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 += 1 # Function to compute LPS array def computeLPSArray(pat, M, lps): len = 0 # length of the previous longest prefix suffix lps[0] = 0 # lps[0] is always 0 i = 1 # the loop calculates lps[i] for i = 1 to M-1 while i if pat[i] == pat[len]: len += 1 lps[i] = len i += 1 else: # This is tricky. Consider the example. # AAACAAAA and i = 7. The idea is similar # to search step. if len != 0: len = lps[len-1] # Also, note that we do not increment i here else: lps[i] = 0 i += 1 # Driver code if __name__ == '__main__': txt = 'ABABDABACDABABCABAB' pat = 'ABABCABAB' KMPSearch(pat, txt) # This code is contributed by Bhavya Jain> |
>
>
C#
// C# program for implementation of KMP pattern> // searching algorithm> using> System;> class> GFG {> >void> KMPSearch(>string> pat,>string> txt)> >{> >int> M = pat.Length;> >int> N = txt.Length;> >// Create lps[] that will hold the longest> >// prefix suffix values for pattern> >int>[] lps =>new> int>[M];> >// Index for pat[]> >int> j = 0;> >// Preprocess the pattern (calculate lps[]> >// array)> >computeLPSArray(pat, M, lps);> >int> i = 0;> >while> ((N - i)>= (M - j)) {> >if> (pat[j] == txt[i]) {> >j++;> >i++;> >}> >if> (j == M) {> >Console.Write(>'Found pattern '> >+>'at index '> + (i - j));> >j = lps[j - 1];> >}> >// Mismatch after j matches> >else> if> (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; } } } void computeLPSArray(string pat, int M, int[] lps) { // Length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // The loop calculates lps[i] for i = 1 to M-1 while (i if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // len = 0 { lps[i] = len; i++; } } } } // Driver code public static void Main() { string txt = 'ABABDABACDABABCABAB'; string pat = 'ABABCABAB'; new GFG().KMPSearch(pat, txt); } } // This code has been contributed by Amit Khandelwal.> |
>
>
Javascript
> >//Javascript program for implementation of KMP pattern> >// searching algorithm> > >function> computeLPSArray(pat, M, lps)> >{> >// length of the previous longest prefix suffix> >var> len = 0;> >var> i = 1;> >lps[0] = 0;>// lps[0] is always 0> > >// the loop calculates lps[i] for i = 1 to M-1> >while> (i if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = len; i++; } } } } function KMPSearch(pat,txt) { var M = pat.length; var N = txt.length; // create lps[] that will hold the longest // prefix suffix values for pattern var lps = []; var j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] // array) computeLPSArray(pat, M, lps); var i = 0; // index for txt[] while ((N - i)>= (M - j)) { if (pat.charAt(j) == txt.charAt(i)) { j++; i++; } if (j == M) { document.write('Знайдений шаблон ' + 'за індексом ' + (i - j) + '
'); j = lps[j - 1]; } // невідповідність після j відповідає else if (i // Не збігаються символи lps[0..lps[j-1]], // вони все одно збігатимуться, якщо (j != 0) j = lps[j - 1 ]; else i = i + 1; } } var txt = 'ABABCABAB'; //Цей код надано shruti456rawal> |
мійлівка
>
>
PHP
// PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) { $M = strlen($pat); $N = strlen($txt); // create lps[] that will hold the longest prefix suffix // values for pattern $lps=array_fill(0,$M,0); // Preprocess the pattern (calculate lps[] array) computeLPSArray($pat, $M, $lps); $i = 0; // index for txt[] $j = 0; // index for pat[] while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++; $i++; } if ($j == $M) { printf('Знайдено шаблон за індексом '.($i - $j)); $j = $lps[$j - 1]; } // невідповідність після j відповідає 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; } } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) { // Length of the previous longest prefix suffix $len = 0; $lps[0] = 0; // lps[0] is always 0 // The loop calculates lps[i] for i = 1 to M-1 $i = 1; while ($i <$M) { if ($pat[$i] == $pat[$len]) { $len++; $lps[$i] = $len; $i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if ($len != 0) { $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 $txt = 'ABABDABACDABABCABAB'; $pat = 'ABABCABAB'; KMPSearch($pat, $txt); // This code is contributed by chandan_jnu ?>> |
>
>Вихід
Found pattern at index 10>
Часова складність: O(N+M), де N — довжина тексту, а M — довжина шаблону, який потрібно знайти.
Допоміжний простір: O(M)