Рубрики

C-программа для алгоритма 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

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

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;

}

Выход:

Found pattern at index 10

Пожалуйста, обратитесь к полной статье по алгоритму KMP для поиска по шаблону для более подробной информации!

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

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

0.00 (0%) 0 votes