История изменений
Исправление invy, (текущая версия) :
сначала по куче искомых строк строится конечный автомат
Называется: описываем регулярный язык, содержащий все нужные слова, регулярным выражением и преобразуем регулярное выражение в недетерминированный конечный автомат (НКА или по английски - NFA), затем используя например алгоритм Томпсона, преобразуем недетерминрованный конечный автомат в детерминированный (ДКА, англ. DFA).
Построение автмоата по регуляронму выражению - вещь элементарная. Конкатенация преобразуется в последовательное соединение автоматов, «|» преобразуются в параллельное включение автоматов. * преобразуются в цикл.
Исправление invy, :
сначала по куче искомых строк строится конечный автомат
Называется: описываем регулярный язык, содержащий все нужные слова, регулярным выражением и преобразуем регулярное выражение в недетерминированный конечный автомат (НКА или по английски - NFA), затем используя например алгоритм Томпсона, преобразуем недетерминрованный конечный автомат в детерминированный (ДКА, англ. DFA).
Построение автмоата по регуляронму выражению - вещь элементарная. Конкатенация преобразуется в последовательное соединение автоматов, «|» преобразуются в параллельное включение автоматов. Все * преобразуются в цикл.
Исходная версия invy, :
сначала по куче искомых строк строится конечный автомат
Называется: описываем регулярный язык, содержащий все нужные слова, регулярным выражением и преобразуем регулярное выражение в недетерминированный конечный автомат (НКА/NFA), затем используя например алгоритм Томпсона, преобразуем недетерминрованный конечный автомат в детерминированный (ДКА/DFA).
Построение автмоата по регуляронму выражению - вещь элементарная. Конкатенация преобразуется в последовательное соединение автоматов, «|» преобразуются в параллельное включение автоматов. Все * преобразуются в цикл.