Рубрики

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

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

Поскольку нам необходимо эффективно вычислять значения хеш-функции для всех подстрок размера m текста, у нас должна быть хеш-функция, которая имеет следующее свойство.
Хеш при следующей смене должен быть эффективно вычисляемым из текущего значения хеша и следующего символа в тексте, или мы можем сказать, что хеш (txt [s + 1 .. s + m]) должен быть эффективно вычисляемым из хеша (txt [s .. s + m-1]) и txt [s + m], т. е. хэш (txt [s + 1 .. s + m]) = перефразировка (txt [s + m], хэш (txt [s .. s + m- 1])) и перефразировка должна быть O (1) операция.

Хэш-функция, предложенная Рабином и Карпом, вычисляет целочисленное значение. Целочисленное значение для строки является числовым значением строки. Например, если все возможные символы от 1 до 10, числовое значение «122» будет 122. Число возможных символов превышает 10 (в общем 256) и длина шаблона может быть большой. Таким образом, числовые значения не могут быть практически сохранены как целое число. Поэтому числовое значение вычисляется с использованием модульной арифметики, чтобы гарантировать, что значения хеш-функции могут быть сохранены в целочисленной переменной (могут помещаться в словах памяти). Чтобы перефразировать, нам нужно снять самую значимую цифру и добавить новую наименее значимую цифру для значения хеша. Перефразировка производится по следующей формуле.

hash (txt [s + 1 .. s + m]) = (d (hash (txt [s .. s + m-1]) — txt [s] * h) + txt [s + m]) mod q

hash (txt [s .. s + m-1]) : значение хеша при сдвиге s .
hash (txt [s + 1 .. s + m]) : значение хеша при следующей смене (или смене s +1)
d : количество символов в алфавите
q : простое число
ч: д ^ (м-1)


Как работает вышеприведенное выражение?

This is simple mathematics, we compute decimal value of current window from previous window.
For example pattern length is 3 and string is “23456”
You compute the value of first window (which is “234”) as 234.
How how will you compute value of next window “345”? You will do (234 – 2*100)*10 + 5 and get 345.

C ++

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

using namespace std;

  
// 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) 

                cout<<"Pattern found at index "<< i<<endl; 

        

  

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

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

        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; 

  
// Это код, предоставленный rathbhupendra

С

/ * Следующая программа - это реализация 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;

}

Джава

// Следующая программа является реализацией Java
// Алгоритма Рабина Карпа, приведенного в книге CLRS

  

public class Main 

{

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

    public final static int d = 256;

      

    / * pat -> pattern

        TXT -> текст

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

    * /

    static void search(String pat, String txt, int q)

    {

        int M = pat.length();

        int N = txt.length();

        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.charAt(i))%q;

            t = (d*t + txt.charAt(i))%q;

        }

      

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

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

        {

      

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

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

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

            if ( p == t )

            {

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

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

                {

                    if (txt.charAt(i+j) != pat.charAt(j))

                        break;

                }

      

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

                if (j == M)

                    System.out.println("Pattern found at index " + i);

            }

      

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

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

            if ( i < N-M )

            {

                t = (d*(t - txt.charAt(i)*h) + txt.charAt(i+M))%q;

      

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

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

                if (t < 0)

                t = (t + q);

            }

        }

    }

      

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

    public static void main(String[] args)

    {

        String txt = "GEEKS FOR GEEKS";

        String pat = "GEEK";

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

        search(pat, txt, q);

    }

}

  
// Этот код предоставлен nuclode

питон

# Следующая программа является реализацией Python
# Алгоритм Рабина Карпа, приведенный в книге CLRS

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

d = 256

  
# pat -> pattern
# txt -> text
# q -> Простое число

  

def search(pat, txt, q):

    M = len(pat)

    N = len(txt)

    i = 0

    j = 0

    p = 0    # хэш-значение для шаблона

    t = 0    # хэш-значение для txt

    h = 1

  

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

    for i in xrange(M-1):

        h = (h*d)%q

  

    # Рассчитать значение хеша шаблона и первого окна

    № текста

    for i in xrange(M):

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

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

  

    # Переместите шаблон поверх текста один за другим

    for i in xrange(N-M+1):

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

        # шаблон, если значения хеша совпадают, тогда проверять только

        # для персонажей по одному

        if p==t:

            # Проверяйте персонажей по одному

            for j in xrange(M):

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

                    break

  

            j+=1

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

            if j==M:

                print "Pattern found at index " + str(i)

  

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

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

        if i < N-M:

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

  

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

            # положительный

            if t < 0:

                t = t+q

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

txt = "GEEKS FOR GEEKS"

pat = "GEEK"

q = 101 # Простое число

search(pat,txt,q)

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

C #

// Следующая программа является реализацией C #
// Алгоритма Рабина Карпа, приведенного в книге CLRS

using System;

public class GFG 

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

    public readonly static int d = 256; 

      

    / * pat -> pattern

        TXT -> текст

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

    * /

    static void search(String pat, String txt, int q) 

    

        int M = pat.Length; 

        int N = txt.Length; 

        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) 

                    Console.WriteLine("Pattern found at index " + i); 

            

      

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

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

            if ( i < N-M ) 

            

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

      

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

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

                if (t < 0) 

                t = (t + q); 

            

        

    

      

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

    public static void Main() 

    

        String txt = "GEEKS FOR GEEKS"

        String pat = "GEEK"

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

        search(pat, txt, q); 

    

  
// Этот код предоставлен PrinciRaj19992

PHP

<?php
// Следующая программа - PHP
// Реализация Рабина Карпа
// Алгоритм, приведенный в книге CLRS

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

$d = 256;

  
/ * pat -> pattern

   TXT -> текст

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

* /

function search($pat, $txt, $q)

{

    $M = strlen($pat);

    $N = strlen($txt);

    $i; $j;

    $p = 0; // хэш-значение

            // для шаблона

    $t = 0; // хэш-значение

            // для текста

    $h = 1;

    $d =1;

  

    // Значение h будет

    // be "pow (d, M-1)% q"

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

        $h = ($h * $d) % $q;

  

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

    // шаблона и первого

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

    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)

                echo "Pattern found at index ",

                                      $i, "\n";

        }

  

        // Рассчитать значение хеша для

        // следующее окно текста:

        // Удалить начальную цифру,

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

        if ($i < $N - $M)

        {

            $t = ($d * ($t - $txt[$i] * 

                        $h) + $txt[$i

                             $M]) % $q;

  

            // Мы можем получить отрицательный

            // значение т, преобразование

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

            if ($t < 0)

            $t = ($t + $q);

        }

    }

}

  
// Код драйвера

$txt = "GEEKS FOR GEEKS";

$pat = "GEEK";

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

search($pat, $txt, $q);

  
// Этот код добавлен
// от ajit
?>


Выход:

Pattern found at index 0
Pattern found at index 10

Среднее и наилучшее время выполнения алгоритма Рабина-Карпа составляет O (n + m), но его наихудшее время составляет O (нм). Наихудший случай алгоритма Рабина-Карпа возникает, когда все символы шаблона и текста совпадают со значениями хеш-функции всех подстрок txt [], совпадающими с хеш-значением pat []. Например, pat [] = «AAA» и txt [] = «AAAAAAA».

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

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

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

0.00 (0%) 0 votes