ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.03.2024
Просмотров: 9
Скачиваний: 0
Федеральное агентство связи
Ордена Трудового Красного Знамени
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра Математической Кибернетики и Информационных Технологий
Отчет по лабораторной работе
по предмету «СиАОД»
на тему:
«Методы поиска подстроки в строке»
Выполнил: студент группы УБСТ2204
Становов Роман Андреевич
Руководитель:
Кутейников Иван Алексеевич
Москва 2023
Цель работы
Реализовать заданный метод поиска подстроки в строке в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию добавления строк, ввода подстроки и поиска подстроки. Предусмотреть возможность существования пробела. Ввести опцию чувствительности / нечувствительности к регистру. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.
Вариант 19
Упрощенный Бойера-Мура
Ход работы
import time
def bad_char_table(pattern):
table = {}
for i in range(len(pattern) - 1):
table[pattern[i]] = len(pattern) - 1 - i
return table
def search_pattern(text, pattern, case_sensitive=True):
if not case_sensitive:
text = text.lower()
pattern = pattern.lower()
n = len(text)
m = len(pattern)
if n < m:
return -1
bad_char = bad_char_table(pattern)
i = m - 1
while i < n:
j = m - 1
while j >= 0 and text[i] == pattern[j]:
i -= 1
j -= 1
if j == -1:
return i + 1
else:
i += max(1, bad_char.get(text[i], m))
return -1
def main():
text = input("Введите строку: ")
pattern = input("Введите подстроку для поиска: ")
case_sensitive = input("Учитывать регистр (да/нет): ").lower()
if case_sensitive == 'да':
case_sensitive = True
else:
case_sensitive = False
start_time = time.time()
result = search_pattern(text, pattern, case_sensitive)
end_time = time.time()
if result != -1:
print(f"Подстрока найдена в позиции {result}")
else:
print("Подстрока не найдена")
search_time = end_time - start_time
print(f"Время выполнения поиска упрощенным методом Бойера-Мура: {search_time} секунд")
start_time = time.time()
if case_sensitive:
result = text.find(pattern)
else:
result = text.lower().find(pattern.lower())
end_time = time.time()
if result != -1:
print(f"Подстрока найдена в позиции {result}")
else:
print("Подстрока не найдена")
python_search_time = end_time - start_time
print(f"Время выполнения поиска методом Python: {python_search_time} секунд")
if __name__ == "__main__":
main()
Результат работы программы: