Мне дали строку T, состоящую только из символов «s», «t», «u», «v». Я хочу найти количество строк длины |T| которая отличается не более чем на n позиции от T. Также каждая такая строка не должна иметь одинаковый символ в трех разных местах, разделенных одинаковым расстоянием. Мой подход заключается в использовании метода динамического программирования, так что dp[i][j][k] обозначает количество таких строк длины i, отличающихся в позиции j и заканчивающихся символом k, где k=s,t,u,v.
if(k совпадает с i-м символом T)
dp[i][j][k]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]- (строки, которые лишние из-за k добавлены в i-м месте и нарушают условие одинакового расстояния)
но я знаю, что это неправильно?
например, для этого предположим, что T = 'sstt', и мы должны найти строки, которые отличаются не более чем в 2 местах, тогда строки, которые не имеют одного и того же символа в трех разных местах, разделенных одинаковым расстоянием, будут «tstt», «ssts» и т. д.
