Изменения
Нет описания правки
next(s):
for (i = length(s); i > 0; i--)
if (s[i] == '('):
break
else
if (s == ""):
return false
s = s +')'
for (j = 1; j <= pointer_opencounter_open; j++):
s = s + '('
for (j = 1; j < pointer_closecounter_close; j++):
s = s + ')'
return true
return num
Пусть теперь разрешены скобки нескольких $k$ типов. Тогда при рассмотрении текущего символа $s[i]$ до пересчёта $\rm depth$ мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $\rm ndepth = \rm depth \pm 1$), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $2n - i - 1$, баланс $\rm ndepth$ и $k$ типов скобок). Утверждается, что формула для этого количества имеет вид:
$d[2n - i - 1][ndepth] \cdot k^{(2n - i - 1 - ndepth) / 2}$