Оптимизация для поиска всех местоположений набора подстрок в строке - PullRequest
0 голосов
/ 06 мая 2020

У меня есть набор подстрок в Python, и я хотел бы найти все вхождения подстрок в строке. Например,

# inputs
needles = {'love', 'hot', 'dogs'}
haystack = "I love hot dogs; hot dogs are delicious."

# output
indexes = {('love', 2), ('hot', 7), ('dog', 11), ('hot', 17), ('dog', 21)}

В настоящее время я использую метод грубой силы для поиска всех вхождений каждой подстроки в строке, что составляет время O (knm), если k, n и m - длина самой длинной строки , количество игл и длину стога сена. Мне интересно, может ли tr ie или любой другой метод ускорить это.

Изменить: многие иглы содержат более одного слова.

1 Ответ

0 голосов
/ 06 мая 2020

Существуют специальные алгоритмы поиска по строкам , предназначенные для поиска нескольких шаблонов в тексте.

Возможно, наиболее известным является Aho-Corasick , и я вижу много Python реализаций (хотя не могу сказать, что лучше). Произвольно найдено .

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...