Рубрики

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

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

Джава

// JAVA-программа для реализации шаблона KMP
// алгоритм поиска

  

class KMP_String_Matching {

    void KMPSearch(String pat, String txt)

    {

        int M = pat.length();

        int N = txt.length();

  

        // создаем lps [], который будет содержать самый длинный

        // Префиксные суффиксные значения для шаблона

        int lps[] = new int[M];

        int j = 0; // индекс для pat []

  

        // Предварительная обработка шаблона (вычисление lps []

        // массив)

        computeLPSArray(pat, M, lps);

  

        int i = 0; // индекс для txt []

        while (i < N) {

            if (pat.charAt(j) == txt.charAt(i)) {

                j++;

                i++;

            }

            if (j == M) {

                System.out.println("Found pattern "

                                   + "at index " + (i - j));

                j = lps[j - 1];

            }

  

            // несоответствие после j совпадений

            else if (i < N && pat.charAt(j) != txt.charAt(i)) {

                // Не совпадают символы lps [0..lps [j-1]],

                // они все равно будут совпадать

                if (j != 0)

                    j = lps[j - 1];

                else

                    i = i + 1;

            }

        }

    }

  

    void computeLPSArray(String pat, int M, int lps[])

    {

        // длина предыдущего длинного суффикса префикса

        int len = 0;

        int i = 1;

        lps[0] = 0; // lps [0] всегда 0

  

        // цикл вычисляет lps [i] для i = 1 до M-1

        while (i < M) {

            if (pat.charAt(i) == pat.charAt(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] = len;

                    i++;

                }

            }

        }

    }

  

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

    public static void main(String args[])

    {

        String txt = "ABABDABACDABABCABAB";

        String pat = "ABABCABAB";

        new KMP_String_Matching().KMPSearch(pat, txt);

    }

}
// Этот код предоставлен Амитом Хандельвалом.

Выход:

Found pattern at index 10

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

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

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

0.00 (0%) 0 votes