Изменения

Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..\ldots j-1]\right]\ </tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма.

Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true\ </tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..\ldots j-1\right]</tex>.

:<tex>a\left[A, i, i+1\right] = true\ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]\ </tex>, иначе <tex>a\left[A, i, i+1\right] = false\ </tex>;

:<tex>a\left[A, i, i\right] = true\ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow \varepsilon\ </tex>, иначе <tex>a\left[A, i, i\right] = false\ </tex>;

:<tex>h\left[A \rightarrow \alpha, i, i, 0\right] = true\ </tex>.

:Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace\ </tex> и <tex>\lbrace k' \mid k' < k \rbrace\ </tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i..\ldots j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)</tex>. То есть, подстроку <tex>w[i..\ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..\ldots r-1\right]</tex>, а подстрока <tex>w[r..\ldots j]</tex> выводится из <tex>k</tex>-го символа правой части правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right]</tex>, но на результат это не повлияет, так как в данный момент <tex>a\left[A,i,j+1\right]=false\ </tex>.

:Но если <tex>\alpha\left[k\right]</tex> {{---}} терминал, то подстроку <tex>w[i..\ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..\ldots r-1\right]\ </tex>, а подстрока <tex>w[r..\ldots j]</tex> выводится, если <tex>w\left[r..\ldots j\right]=\alpha\left[k\right]\ </tex>.

:Базовая динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right]\ </tex>. То есть, подстроку <tex>w[i..\ldots j-1]\ </tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i..\ldots j-1\right]</tex>, .

:После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.

Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right]\ </tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.

Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</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> памяти.