Рубрики

Алгоритм KMP для поиска по шаблону

Учитывая текст txt [0..n-1] и шаблон pat [0..m-1] , напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [] в txt. [] . Вы можете предположить, что n> m .

Примеры:

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Поиск по шаблону является важной проблемой в информатике. Когда мы ищем строку в файле блокнота / слова, в браузере или в базе данных, для отображения результатов поиска используются алгоритмы поиска по шаблону.

Мы обсуждали алгоритм поиска Наивного шаблона в предыдущем посте . Наихудшая сложность алгоритма Наива — O (m (n-m + 1)). Временная сложность алгоритма KMP в худшем случае составляет O (n).

KMP (Кнут Моррис Пратт) Поиск шаблонов
Алгоритм поиска шаблонов Naive не работает должным образом в случаях, когда мы видим много совпадающих символов, за которыми следует несовпадающий символ. Ниже приведены некоторые примеры.

   txt[] = "AAAAAAAAAAAAAAAAAB"
   pat[] = "AAAAB"

   txt[] = "ABABABCABABABCABABABC"
   pat[] =  "ABABAC" (not a worst case, but a bad case for Naive)

Алгоритм сопоставления KMP использует вырождающееся свойство (шаблон, имеющий одни и те же под-шаблоны, появляющиеся в шаблоне более одного раза) шаблона и улучшающий сложность наихудшего случая до O (n). Основная идея алгоритма KMP заключается в следующем: всякий раз, когда мы обнаруживаем несоответствие (после некоторых совпадений), мы уже знаем некоторые символы в тексте следующего окна. Мы используем эту информацию, чтобы избежать совпадения символов, которые, как мы знаем, будут совпадать. Давайте рассмотрим пример ниже, чтобы понять это.

Matching Overview
txt = "AAAAABAAABA" 
pat = "AAAA"

We compare first window of txt with pat
txt = "AAAAABAAABA" 
pat = "AAAA"  [Initial position]
We find a match. This is same as Naive String Matching.

In the next step, we compare next window of txt with pat.
txt = "AAAAABAAABA" 
pat =  "AAAA" [Pattern shifted one position]
This is where KMP does optimization over Naive. In this 
second window, we only compare fourth A of pattern
with fourth character of current window of text to decide 
whether current window matches or not. Since we know 
first three characters will anyway match, we skipped 
matching first three characters. 

Need of Preprocessing?
An important question arises from the above explanation, 
how to know how many characters to be skipped. To know this, 
we pre-process pattern and prepare an integer array 
lps[] that tells us the count of characters to be skipped. 

Обзор предварительной обработки:

  • Алгоритм KMP предварительно обрабатывает pat [] и создает вспомогательный lps [] размером m (такой же, как размер шаблона), который используется для пропуска символов при сопоставлении.
  • Имя 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] = the longest proper prefix of pat[0..i] 
                  which is also a suffix of pat[0..i]. 
  • Примечание: lps [i] также может быть определен как самый длинный префикс, который также является правильным суффиксом. Нам нужно правильно использовать в одном месте, чтобы убедиться, что вся подстрока не рассматривается.

Examples of lps[] construction:
For the pattern “AAAA”, 
lps[] is [0, 1, 2, 3]

For the pattern “ABCDE”, 
lps[] is [0, 0, 0, 0, 0]

For the pattern “AABAACAABAA”, 
lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

For the pattern “AAACAAAAAC”, 
lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4] 

For the pattern “AAABAAA”, 
lps[] is [0, 1, 2, 0, 1, 2, 3]

Алгоритм поиска:
В отличие от наивного алгоритма , где мы скользим по шаблону по одному и сравниваем все символы в каждой смене, мы используем значение из lps [], чтобы определить, какие из следующих символов должны быть сопоставлены. Идея состоит в том, чтобы не соответствовать персонажу, который, как мы знаем, в любом случае будет соответствовать.

Как использовать lps [] для определения следующих позиций (или для определения количества пропускаемых символов)?

  • Мы начинаем сравнение pat [j] с j = 0 с символами текущего окна текста.
  • Мы сохраняем совпадающие символы txt [i] и pat [j] и продолжаем увеличивать i и j, в то время как pat [j] и txt [i] продолжают совпадать .
  • Когда мы видим несоответствие
    • Мы знаем, что символы pat [0..j-1] совпадают с txt [ij… i-1] (обратите внимание, что j начинается с 0 и увеличивает его только в случае совпадения).
    • Мы также знаем (из приведенного выше определения), что lps [j-1] — это число символов pat [0… j-1], которые являются как собственным префиксом, так и суффиксом.
    • Из вышеупомянутых двух пунктов мы можем заключить, что нам не нужно сопоставлять эти символы lps [j-1] с txt [ij… i-1], потому что мы знаем, что эти символы в любом случае будут совпадать. Давайте рассмотрим приведенный выше пример, чтобы понять это.
txt[] = "AAAAABAAABA" 
pat[] = "AAAA"
lps[] = {0, 1, 2, 3} 

i = 0, j = 0
txt[] = "AAAAABAAABA" 
pat[] = "AAAA"
txt[i] and pat[j] match, do i++, j++

i = 1, j = 1
txt[] = "AAAAABAAABA" 
pat[] = "AAAA"
txt[i] and pat[j] match, do i++, j++

i = 2, j = 2
txt[] = "AAAAABAAABA" 
pat[] = "AAAA"
pat[i] and pat[j] match, do i++, j++

i = 3, j = 3
txt[] = "AAAAABAAABA" 
pat[] = "AAAA"
txt[i] and pat[j] match, do i++, j++

i = 4, j = 4
Since j == M, print pattern found and reset j,
j = lps[j-1] = lps[3] = 3

Here unlike Naive algorithm, we do not match first three 
characters of this window. Value of lps[j-1] (in above 
step) gave us index of next character to match.
i = 4, j = 3
txt[] = "AAAAABAAABA" 
pat[] =  "AAAA"
txt[i] and pat[j] match, do i++, j++

i = 5, j = 4
Since j == M, print pattern found and reset j,
j = lps[j-1] = lps[3] = 3

Again unlike Naive algorithm, we do not match first three 
characters of this window. Value of lps[j-1] (in above 
step) gave us index of next character to match.
i = 5, j = 3
txt[] = "AAAAABAAABA" 
pat[] =   "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[2] = 2

i = 5, j = 2
txt[] = "AAAAABAAABA" 
pat[] =    "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[1] = 1 

i = 5, j = 1
txt[] = "AAAAABAAABA" 
pat[] =     "AAAA"
txt[i] and pat[j] do NOT match and j > 0, change only j
j = lps[j-1] = lps[0] = 0

i = 5, j = 0
txt[] = "AAAAABAAABA" 
pat[] =      "AAAA"
txt[i] and pat[j] do NOT match and j is 0, we do i++.

i = 6, j = 0
txt[] = "AAAAABAAABA" 
pat[] =       "AAAA"
txt[i] and pat[j] match, do i++ and j++

i = 7, j = 1
txt[] = "AAAAABAAABA" 
pat[] =       "AAAA"
txt[i] and pat[j] match, do i++ and j++

We continue this way...

C ++

// C ++ программа для реализации поиска по шаблону KMP
// алгоритм
#include <bits/stdc++.h>

  

void computeLPSArray(char* pat, int M, int* lps);

  
// Печатает вхождения txt [] в pat []

void KMPSearch(char* pat, char* txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

  

    // создаем lps [], который будет содержать самый длинный суффикс префикса

    // значения для шаблона

    int lps[M];

  

    // Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray(pat, M, lps);

  

    int i = 0; // индекс для txt []

    int j = 0; // индекс для pat []

    while (i < N) {

        if (pat[j] == txt[i]) {

            j++;

            i++;

        }

  

        if (j == M) {

            printf("Found pattern at index %d ", i - j);

            j = lps[j - 1];

        }

  

        // несоответствие после j совпадений

        else if (i < N && pat[j] != txt[i]) {

            // Не совпадают символы lps [0..lps [j-1]],

            // они все равно будут совпадать

            if (j != 0)

                j = lps[j - 1];

            else

                i = i + 1;

        }

    }

}

  
// Заполняет lps [] для данного patttern pat [0..M-1]

void computeLPSArray(char* pat, int M, int* lps)

{

    // длина предыдущего длинного суффикса префикса

    int len = 0;

  

    lps[0] = 0; // lps [0] всегда 0

  

    // цикл вычисляет lps [i] для i = 1 до M-1

    int i = 1;

    while (i < M) {

        if (pat[i] == pat[len]) {

            len++;

            lps[i] = len;

            i++;

        }

        else // (pat [i]! = pat [len])

        {

            // Это сложно. Рассмотрим пример.

            // AAACAAAA и i = 7. Идея похожа

            // искать шаг.

            if (len != 0) {

                len = lps[len - 1];

  

                // Также обратите внимание, что мы не увеличиваем

                // я здесь

            }

            else // if (len == 0)

            {

                lps[i] = 0;

                i++;

            }

        }

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char txt[] = "ABABDABACDABABCABAB";

    char pat[] = "ABABCABAB";

    KMPSearch(pat, txt);

    return 0;

}

Джава

// JAVA-программа для реализации шаблона KMP
// алгоритм поиска

  

class KMP_String_Matching {

    void KMPSearch(String pat, String txt)

    {

        int M = pat.length();

        int N = txt.length();

  

        // создаем lps [], который будет содержать самый длинный

        // Префиксные суффиксные значения для шаблона

        int lps[] = new int[M];

        int j = 0; // индекс для pat []

  

        // Предварительная обработка шаблона (вычисление lps []

        // массив)

        computeLPSArray(pat, M, lps);

  

        int i = 0; // индекс для txt []

        while (i < N) {

            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];

            }

  

            // несоответствие после j совпадений

            else if (i < N && pat.charAt(j) != txt.charAt(i)) {

                // Не совпадают символы lps [0..lps [j-1]],

                // они все равно будут совпадать

                if (j != 0)

                    j = lps[j - 1];

                else

                    i = i + 1;

            }

        }

    }

  

    void computeLPSArray(String pat, int M, int lps[])

    {

        // длина предыдущего длинного суффикса префикса

        int len = 0;

        int i = 1;

        lps[0] = 0; // lps [0] всегда 0

  

        // цикл вычисляет lps [i] для i = 1 до M-1

        while (i < M) {

            if (pat.charAt(i) == pat.charAt(len)) {

                len++;

                lps[i] = len;

                i++;

            }

            else // (pat [i]! = pat [len])

            {

                // Это сложно. Рассмотрим пример.

                // AAACAAAA и i = 7. Идея похожа

                // искать шаг.

                if (len != 0) {

                    len = lps[len - 1];

  

                    // Также обратите внимание, что мы не увеличиваем

                    // я здесь

                }

                else // if (len == 0)

                {

                    lps[i] = len;

                    i++;

                }

            }

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        String txt = "ABABDABACDABABCABAB";

        String pat = "ABABCABAB";

        new KMP_String_Matching().KMPSearch(pat, txt);

    }

}
// Этот код предоставлен Амитом Хандельвалом.

питон

# Python программа для алгоритма KMP

def KMPSearch(pat, txt):

    M = len(pat)

    N = len(txt)

  

    # create lps [], который будет содержать самый длинный суффикс префикса

    # значения для шаблона

    lps = [0]*M

    j = 0 # index для pat []

  

    # Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray(pat, M, lps)

  

    i = 0 # index для txt []

    while i < N:

        if pat[j] == txt[i]:

            i += 1

            j += 1

  

        if j == M:

            print "Found pattern at index " + str(i-j)

            j = lps[j-1]

  

        # несоответствие после j матчей

        elif i < N and pat[j] != txt[i]:

            # Не совпадать с символами lps [0..lps [j-1]],

            # они будут совпадать в любом случае

            if j != 0:

                j = lps[j-1]

            else:

                i += 1

  

def computeLPSArray(pat, M, lps):

    len = 0 # длина предыдущего длинного суффикса префикса

  

    lps[0] # lps [0] всегда 0

    i = 1

  

    # цикл вычисляет lps [i] для i = 1 до M-1

    while i < M:

        if pat[i]== pat[len]:

            len += 1

            lps[i] = len

            i += 1

        else:

            # Это сложно. Рассмотрим пример.

            # AAACAAAA и я = 7. Идея похожа

            # к шагу поиска.

            if len != 0:

                len = lps[len-1]

  

                # Также обратите внимание, что мы не увеличиваем i здесь

            else:

                lps[i] = 0

                i += 1

  

txt = "ABABDABACDABABCABAB"

pat = "ABABCABAB"

KMPSearch(pat, txt)

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для реализации шаблона KMP
// алгоритм поиска

using System;

  

class GFG {

  

    void KMPSearch(string pat, string txt)

    {

        int M = pat.Length;

        int N = txt.Length;

  

        // создаем lps [], который будет содержать самый длинный

        // Префиксные суффиксные значения для шаблона

        int[] lps = new int[M];

        int j = 0; // индекс для pat []

  

        // Предварительная обработка шаблона (вычисление lps []

        // массив)

        computeLPSArray(pat, M, lps);

  

        int i = 0; // индекс для txt []

        while (i < N) {

            if (pat[j] == txt[i]) {

                j++;

                i++;

            }

            if (j == M) {

                Console.Write("Found pattern "

                              + "at index " + (i - j));

                j = lps[j - 1];

            }

  

            // несоответствие после j совпадений

            else if (i < N && pat[j] != txt[i]) {

                // Не совпадают символы lps [0..lps [j-1]],

                // они все равно будут совпадать

                if (j != 0)

                    j = lps[j - 1];

                else

                    i = i + 1;

            }

        }

    }

  

    void computeLPSArray(string pat, int M, int[] lps)

    {

        // длина предыдущего длинного суффикса префикса

        int len = 0;

        int i = 1;

        lps[0] = 0; // lps [0] всегда 0

  

        // цикл вычисляет lps [i] для i = 1 до M-1

        while (i < M) {

            if (pat[i] == pat[len]) {

                len++;

                lps[i] = len;

                i++;

            }

            else // (pat [i]! = pat [len])

            {

                // Это сложно. Рассмотрим пример.

                // AAACAAAA и i = 7. Идея похожа

                // искать шаг.

                if (len != 0) {

                    len = lps[len - 1];

  

                    // Также обратите внимание, что мы не увеличиваем

                    // я здесь

                }

                else // if (len == 0)

                {

                    lps[i] = len;

                    i++;

                }

            }

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        string txt = "ABABDABACDABABCABAB";

        string pat = "ABABCABAB";

        new GFG().KMPSearch(pat, txt);

    }

}

  
// Этот код предоставлен Амитом Хандельвалом.

PHP

<?php
// PHP программа для реализации поиска по шаблону KMP
// алгоритм

  

  
// Печатает вхождения txt [] в pat []

function KMPSearch($pat, $txt)

{

    $M = strlen($pat);

    $N = strlen($txt);

  

    // создаем lps [], который будет содержать самый длинный суффикс префикса

    // значения для шаблона

    $lps=array_fill(0,$M,0);

  

    // Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray($pat, $M, $lps);

  

    $i = 0; // индекс для txt []

    $j = 0; // индекс для pat []

    while ($i < $N) {

        if ($pat[$j] == $txt[$i]) {

            $j++;

            $i++;

        }

  

        if ($j == $M) {

            printf("Found pattern at index ".($i - $j));

            $j = $lps[$j - 1];

        }

  

        // несоответствие после j совпадений

        else if ($i < $N && $pat[$j] != $txt[$i]) {

            // Не совпадают символы lps [0..lps [j-1]],

            // они все равно будут совпадать

            if ($j != 0)

                $j = $lps[$j - 1];

            else

                $i = $i + 1;

        }

    }

}

  
// Заполняет lps [] для данного patttern pat [0..M-1]

function computeLPSArray($pat, $M, &$lps)

{

    // длина предыдущего длинного суффикса префикса

    $len = 0;

  

    $lps[0] = 0; // lps [0] всегда 0

  

    // цикл вычисляет lps [i] для i = 1 до M-1

    $i = 1;

    while ($i < $M) {

        if ($pat[$i] == $pat[$len]) {

            $len++;

            $lps[$i] = $len;

            $i++;

        }

        else // (pat [i]! = pat [len])

        {

            // Это сложно. Рассмотрим пример.

            // AAACAAAA и i = 7. Идея похожа

            // искать шаг.

            if ($len != 0) {

                $len = $lps[$len - 1];

  

                // Также обратите внимание, что мы не увеличиваем

                // я здесь

            }

            else // if (len == 0)

            {

                $lps[$i] = 0;

                $i++;

            }

        }

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

  

    $txt = "ABABDABACDABABCABAB";

    $pat = "ABABCABAB";

    KMPSearch($pat, $txt);

      
// Этот код предоставлен chandan_jnu
?>


Выход:

Found pattern at index 10

Алгоритм предварительной обработки:
В части предварительной обработки мы вычисляем значения в lps []. Для этого мы отслеживаем длину самого длинного значения суффикса префикса (мы используем переменную len для этой цели) для предыдущего индекса. Мы инициализируем lps [0] и len как 0. Если pat [len] и pat [i] совпадают, мы увеличиваем len на 1 и присваиваем увеличенное значение lps [i]. Если pat [i] и pat [len] не совпадают и len не равно 0, мы обновляем len до lps [len-1]. Подробности смотрите в computeLPSArray () в приведенном ниже коде.

Иллюстрация предварительной обработки (или построения lps [])

pat[] = "AAACAAAA"

len = 0, i  = 0.
lps[0] is always 0, we move 
to i = 1

len = 0, i  = 1.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 1, lps[1] = 1, i = 2

len = 1, i  = 2.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 2, lps[2] = 2, i = 3

len = 2, i  = 3.
Since pat[len] and pat[i] do not match, and len > 0, 
set len = lps[len-1] = lps[1] = 1

len = 1, i  = 3.
Since pat[len] and pat[i] do not match and len > 0, 
len = lps[len-1] = lps[0] = 0

len = 0, i  = 3.
Since pat[len] and pat[i] do not match and len = 0, 
Set lps[3] = 0 and i = 4.
We know that characters pat
len = 0, i  = 4.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 1, lps[4] = 1, i = 5

len = 1, i  = 5.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 2, lps[5] = 2, i = 6

len = 2, i  = 6.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 3, lps[6] = 3, i = 7

len = 3, i  = 7.
Since pat[len] and pat[i] do not match and len > 0,
set len = lps[len-1] = lps[2] = 2

len = 2, i  = 7.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 3, lps[7] = 3, i = 8

We stop here as we have constructed the whole lps[].

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

Рекомендуемые посты:

Алгоритм KMP для поиска по шаблону

0.00 (0%) 0 votes