Рубрики

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

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

питон

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

Выход:

Pattern found at index 0
Pattern found at index 10

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

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

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

0.00 (0%) 0 votes