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

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

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

источник

2016-10-02 Jarvis

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

Можете ли вы четко объяснить некоторым псевдо-кодом, какие точные изменения следует делать в KMP-алгоритме? – Jarvis

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

источник

2016-11-20 01:07:14 Jarvis

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

ответ

Смежные вопросы