Рубрики

Программа Python для поиска подстроки в анаграмме (или поиск всех перестановок)

Учитывая текст txt [0..n-1] и шаблон pat [0..m-1], напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [] и его перестановки (или анаграммы) в txt []. Вы можете предположить, что n> m.
Ожидаемая сложность времени O (n)

Примеры:

1) Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"
   Output:   Found at Index 0
             Found at Index 5
             Found at Index 6
2) Input: txt[] =  "AAABABAA" pat[] = "AABA"
   Output:   Found at Index 0
             Found at Index 1
             Found at Index 4

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простая идея — модифицировать алгоритм Рабина Карпа . Например, мы можем сохранить значение хеш-функции как сумму значений ASCII всех символов по модулю большого простого числа. Для каждого символа текста мы можем добавить текущий символ к значению хеша и вычесть первый символ предыдущего окна. Это решение выглядит хорошо, но, как и в случае со стандартным Рабином Карпом, временная сложность этого решения в наихудшем случае — O (mn). Наихудший случай возникает, когда все значения хеш-функции совпадают, и мы одно за другим сопоставляем все символы.
Мы можем достичь O (n) временной сложности, предполагая, что размер алфавита фиксирован, что, как правило, верно, поскольку у нас есть максимально 256 возможных символов в ASCII. Идея состоит в том, чтобы использовать два массива счета:

1) Первый массив подсчета хранит частоты символов в шаблоне.
2) Второй массив подсчета хранит частоты символов в текущем окне текста.

Важно отметить, что временная сложность сравнения двух массивов счетчиков равна O (1), поскольку количество элементов в них фиксировано (независимо от размера рисунка и текста). Ниже приведены шаги этого алгоритма.
1) Сохранение подсчетов частот паттерна в первом массиве countP [] . Также храните подсчеты частот символов в первом окне текста в массиве countTW [] .

2) Теперь запустите цикл от i = M до N-1. Делайте следующее в цикле.
… ..A) Если два массива подсчета идентичны, мы нашли случай.
… ..B) Увеличение счетчика текущего символа текста в countTW []
… ..C) Уменьшить счетчик первого символа в предыдущем окне в countWT []

3) Последнее окно не проверяется вышеуказанным циклом, поэтому проверьте его явно.

python3

# Python программа для поиска всех
# анаграммы шаблона в тексте

  

MAX = 256 

  
# Эта функция возвращает true
# если содержимое arr1 [] и arr2 []
# одинаковы, в противном случае ложь.

def compare(arr1, arr2):

    for i in range(MAX):

        if arr1[i] != arr2[i]:

            return False

    return True

      
# Эта функция поиска для всех
# перестановки pat [] в txt []

def search(pat, txt):

  

    M = len(pat)

    N = len(txt)

  

    # countP []: Сохранить количество

    # все символы шаблона

    # countTW []: Сохранить количество

    # текущее окно текста

    countP = [0]*MAX

  

    countTW = [0]*MAX

  

    for i in range(M):

        (countP[ord(pat[i]) ]) += 1

        (countTW[ord(txt[i]) ]) += 1

  

    # Пройдите через оставшиеся

    # символов шаблона

    for i in range(M, N):

  

        # Сравнить количество текущих

        # окно текста с

        # количество паттернов []

        if compare(countP, countTW):

            print("Found at Index", (i-M))

  

        # Добавить текущий символ в текущее окно

        (countTW[ ord(txt[i]) ]) += 1

  

        # Удалить первый символ предыдущего окна

        (countTW[ ord(txt[i-M]) ]) -= 1

      

    # Проверьте последнее окно в тексте

    if compare(countP, countTW):

        print("Found at Index", N-M)

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

txt = "BACDGABCDA"

pat = "ABCD"       
search(pat, txt)   

  
# Этот код добавлен
# Упендра Сингх Бартвал

Выход:

('Found at Index', 0)
('Found at Index', 5)
('Found at Index', 6)

Пожалуйста, обратитесь к полной статье о поиске подстроки Anagram (или Поиск всех перестановок) для более подробной информации!

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

Программа Python для поиска подстроки в анаграмме (или поиск всех перестановок)

0.00 (0%) 0 votes