Изменения
Нет описания правки
== Оценка сложности ==
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.
Обработки правил вида <tex>A \rightarrow w[i]</tex> и <tex>A \rightarrow \varepsilon</tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.
<tex>h\left[A \rightarrow \alpha, i, i, 0\right]</tex> за <tex>O(n \cdot |\Gamma|)</tex>. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>.
Расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex> времени, основной динамики — <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex> памяти.
