Рубрики

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

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

питон

# Python программа для алгоритма KMP

def KMPSearch(pat, txt):

    M = len(pat)

    N = len(txt)

  

    # create lps [], который будет содержать самый длинный суффикс префикса

    # значения для шаблона

    lps = [0]*M

    j = 0 # index для pat []

  

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

    computeLPSArray(pat, M, lps)

  

    i = 0 # index для txt []

    while i < N:

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

            i += 1

            j += 1

  

        if j == M:

            print "Found pattern at index " + str(i-j)

            j = lps[j-1]

  

        # несоответствие после j матчей

        elif i < N and pat[j] != txt[i]:

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

            # они будут совпадать в любом случае

            if j != 0:

                j = lps[j-1]

            else:

                i += 1

  

def computeLPSArray(pat, M, lps):

    len = 0 # длина предыдущего длинного суффикса префикса

  

    lps[0] # lps [0] всегда 0

    i = 1

  

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

    while i < M:

        if pat[i]== pat[len]:

            len += 1

            lps[i] = len

            i += 1

        else:

            # Это сложно. Рассмотрим пример.

            # AAACAAAA и я = 7. Идея похожа

            # к шагу поиска.

            if len != 0:

                len = lps[len-1]

  

                # Также обратите внимание, что мы не увеличиваем i здесь

            else:

                lps[i] = 0

                i += 1

  

txt = "ABABDABACDABABCABAB"

pat = "ABABCABAB"

KMPSearch(pat, txt)

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

Выход:

Found pattern at index 10

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

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

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

0.00 (0%) 0 votes