418
правок
Изменения
м
→Алгоритм
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив <tex>d</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> - константа и <tex>m < n</tex>. <tex>|w| = n</tex>.
=== Шаг 1. База ===
