418
правок
Изменения
→Псевдокод
== Псевдокод ==
'''boolean''' CYK('''char'''[] w, '''list''' <tex>\Gamma</tex>, '''int''' S)
'''int''' n = length(w)
'''boolean''' d[<tex>|\Gamma|</tex>][n][n]
'''for''' i = 1 ... n
'''for''' (A <tex>\rightarrow</tex> w[i] <tex>\in</tex> <tex>\Gamma</tex>)
d[A,i,i] = true
'''for''' len = 1 .. n - 1
'''for''' i = 1 .. n - len
'''for''' (A <tex>\rightarrow</tex> BC <tex>\in</tex> <tex>\Gamma</tex>)
'''for''' k = i .. i + len - 1
d[A][i][i + len] = d[A][i][i + len] '''or''' d[B][i][k] '''and''' d[C][k + 1][i + len]
'''return''' d[S][1][n]
== Асимптотика ==
