Рубрики

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

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

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

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

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

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

0.00 (0%) 0 votes