Рубрики

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

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

Джава

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

Выход:

Pattern found at index 0
Pattern found at index 10

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

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

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

0.00 (0%) 0 votes