У меня есть набор подстрок в 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 или любой другой метод ускорить это.
Изменить: многие иглы содержат более одного слова.