алгоритм рабина-карпа на Python. Поиск образца в тексте алгоритм РабинаКарпа
 Скачать 381.89 Kb.
|
|
МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра МО ЭВМ ОТЧЕТ по лабораторной работе №4 по дисциплине Алгоритмы и структуры данных Тема: Поиск образца в тексте алгоритм Рабина-Карпа Студент(ка) гр. 1381 Денисова О.К. Преподаватель Иванов Д.В. Санкт-Петербург 2022 2 Цель работы Изучить хэш-таблицы, их виды, а также хэш-функции, и написать программу, находящую подстроку в строке с использованием хэш-функции. Общая формулировка задачи Напишите программу, которая ищет все вхождения строки Pattern в строку Text, используя алгоритм Карпа-Рабина. На вход программе подается подстрока Pattern и текст Text. Необходимо вывести индексы вхождений строки Pattern в строку Text в возрастающем порядке, используя индексацию с нуля. Примечание в работе запрещено использовать библиотечные реализации алгоритмов и структур Формат входа Первая строка входа содержит строку Pattern. Вторая строка содержит строку Text. Формат выхода Выход должен содержать индексы вхождений строки Pattern в возрастающем порядке, используя индексацию с нуля. Выполнение работы Входе выполнения лабораторной работы была написана программа, решающая поставленную задачу. Была реализована функция hashing, принимающая в качестве аргументов строку, значение x и значение p. Функция 3 возвращает хэш-значение данной строки, а именно полиномиальный хэш, взятый по модулю p. В функции main находится реализация алгоритма Рабина-Карпа: сначала вычисляется хэш-значение строки-паттерна, затем вычисляются хэш-значения окон подходящей длины, после чего происходит сравнение хэш-значений: если хэш паттерна и хэш окна совпали, тогда проверяется совпадение паттерна и подстроки, иначе эта операция не выполняется. Индексы найденных вхождений добавляются в результирующий список answer. Юнит-тестирование № Входные данные Выходные данные Описание теста 1 'aba' 'abacaba' [0, 4] Тривиальный тест с двумя вхождениями паттерна в строку 2 'kkk' 'kkkkkkk' [0, 1, 2, 3, 4] Тест с максимальным количеством вхождения паттерна в строку 3 'abc' 'gggggg' [] Тест, содержащий 0 вхождений паттерна в строку 4 4 'hf' 'fhafha' [] Тест, в котором строка-текст содержит инвертированные строки-паттерны 5 '' 'abcde' [] Тест, содержащий пустой паттерн 6 'a' '' [] Тест, содержащий пустую строку- текст 7 '' '' [] Тест с пустым паттерном и пустой строкой- текст Выводы Входе выполнения лабораторной работы были приобретены знания о хэш-таблицах и их видах, хэш-функциях, и была реализована программа, решающая поставленную задачу с помощью алгоритма Рабина-Карпа: поиск подстроки в строке с использованием сравнений по хэш-значениям. 5 ПРИЛОЖЕНИЕ А ИСХОДНЫЙ КОД ПРОГРАММЫ ФАЙЛ MAIN.PY from functools import reduce def hashing(string, x, p): return reduce(lambda temp, c: (temp * x + ord(c)) % p, string, 0) % p def main(pattern, text): if not pattern: return [] pattern_len, text_len = len(pattern), len(text) answer = [] x = 13 p = 1000000007 pattern_hash = hashing(pattern, x, p) hashs = [hashing(text[i:i+pattern_len], x, p) for i in range(text_len - pattern_len + 1)] for i in range(len(hashs)): if (hashs[i] == pattern_hash) and (text[i: i+pattern_len] == pattern): answer.append(i) return answer print(*main(input(), input()), sep=' ') 6 ПРИЛОЖЕНИЕ Б ЮНИТ-ТЕСТИРОВАНИЕ ФАЙЛ TESTS.PY import unittest from main import main class MyTestCase(unittest.TestCase): def test1(self): self.assertEqual(main('aba', 'abacaba'), [0, 4]) def test2(self): self.assertEqual(main('kkk', 'kkkkkkk'), [0, 1, 2, 3, 4]) def test3(self): self.assertEqual(main('abc', 'gggggg'), []) def test4(self): self.assertEqual(main('hf', 'fhafha'), []) def test5(self): self.assertEqual(main('', 'abcde'), []) def test6(self): self.assertEqual(main('a', ''), []) def test7(self): self.assertEqual(main('', ''), []) if __name__ == '__main__': unittest.main() |