Рубрики

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

Учитывая текст 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

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

1) Сам шаблон.
2) Все подстроки текста длиной m.

C / C ++

/ * Следующая программа - это реализация C Рабина Карпа
Алгоритм приведен в книге CLRS * /
#include <stdio.h>
#include <string.h>

  
// d - количество символов во входном алфавите
#define d 256

  
/ * pat -> pattern

    TXT -> текст

    q -> простое число

* /

void search(char pat[], char txt[], int q)

{

    int M = strlen(pat);

    int N = strlen(txt);

    int i, j;

    int p = 0; // хеш-значение для шаблона

    int t = 0; // хеш-значение для txt

    int h = 1;

  

    // Значение h будет "pow (d, M-1)% q"

    for (i = 0; i < M - 1; i++)

        h = (h * d) % q;

  

    // Вычисляем значение хеша pattern и first

    // окно текста

    for (i = 0; i < M; i++) {

        p = (d * p + pat[i]) % q;

        t = (d * t + txt[i]) % q;

    }

  

    // Скользим шаблон по тексту один за другим

    for (i = 0; i <= N - M; i++) {

  

        // Проверяем значения хеш-функции текущего окна текста

        // и шаблон. Если значения хеша совпадают, то только

        // проверяем наличие символов по одному

        if (p == t) {

            / * Проверять символы по одному * /

            for (j = 0; j < M; j++) {

                if (txt[i + j] != pat[j])

                    break;

            }

  

            // если p == t и pat [0 ... M-1] = txt [i, i + 1, ... i + M-1]

            if (j == M)

                printf("Pattern found at index %d \n", i);

        }

  

        // Рассчитать значение хеша для следующего окна текста: Удалить

        // начальная цифра, добавляем завершающую цифру

        if (i < N - M) {

            t = (d * (t - txt[i] * h) + txt[i + M]) % q;

  

            // Мы можем получить отрицательное значение t, преобразовав его

            // к положительному

            if (t < 0)

                t = (t + q);

        }

    }

}

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

int main()

{

    char txt[] = "GEEKS FOR GEEKS";

    char pat[] = "GEEK";

    int q = 101; // Простое число

    search(pat, txt, q);

    return 0;

}

Выход:

Pattern found at index 0 
Pattern found at index 10

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

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

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

0.00 (0%) 0 votes