Блог

Главная - Вопросы по программированию - Обработка оператора подстановочных знаков ‘*’ при сопоставлении строк с использованием KMP-алгоритма?

Обработка оператора подстановочных знаков ‘*’ при сопоставлении строк с использованием KMP-алгоритма?

#algorithm #string-matching #knuth-morris-pratt

#алгоритм #сопоставление строк #кнут-моррис-Пратт

Вопрос:

Как мне следует обращаться со случаем, когда сопоставляемый шаблон содержит подстановочный знак, * , например , AB*C , который присутствует в тексте ABEFGCS (здесь * используются символы EFG ), используя KMP-алгоритм?

Какая модификация в алгоритме может решить эту проблему?

Комментарии:

1. * жаден по натуре.. Я бы просто сопоставил AB в тексте, а затем C после AB.

Ответ №1:

На самом деле я понял, оставив ответ для справки, мы можем просто разбить строку об операторе подстановки, применить KMP к каждой части и проверить, является ли каждая часть вложенной строкой или нет, также, являются ли части смежными или нет, можно проверить за линейное время, следовательно, общее времясложность по-прежнему линейна.

Комментарии:

1. Мой анализ временной сложности при наличии k звездочки: разбейте pattern строку на большую k 1 часть, выполните поиск по каждому подшаблону в target text k 1 отсортированных индексах. Создайте k монотонный указатель, подобный которому в mergesort, это может найти все совпадения во времени O(km n) и пространстве O(k n) (например, в python combine next и yield ). Где m — длина text строки, n — длина pattern строки.