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

01.01.2020Программы 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