ДЗ:
Конечный автомат и алгоритм Кнтуа-Морриса-Пратта
- Реализовать алгоритм вычисления функции переходов для паттерна, работающий за время O(m^3 * |Sigma|)
Дополнительно:
- Реализовать при помощи оптимизации по поиску префиксов, аналогичному алгоритму КМП, алгоритм для составления конечного автомата за O(m * |Sigma|)
- Разобрать 2 примера работы алгоритма на разных строках (ориентироваться на строку длиной 5-7 символов), в которых при этом есть префиксы, одновременно являющиеся суффиксами
Критерии оценки: - Алгоритм по составлению функции переходов написан верно - 3 балла
- За каждое дополнительное задание - 1 балл (все нарисованные автоматы считаются за одно задание :) )