299
правок
Изменения
→Псевдокод
Перед вызовом процедуры заполняем <tex>L[][]</tex> начальными значениями: <tex>L[i][j] = 1</tex> если <tex>i=j</tex>, <tex>L[i][j] = 0</tex>, если <tex>i>j</tex>, в остальных случаях <tex>L[i][j]=-1</tex>.
При первой вызове функции, к качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 вызов функции будет иметь следующий вид: <tex>palSubSeq(0,6)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>, где <tex>N</tex> — длина исходной строки.
'''Функция для вычисления длины палиндрома (<tex>left, right</tex> - границы исходной последовательности):'''
<code style = "display: inline-block;">
'''palSubSeq'''(left, right)
L[left][right] = MAX(palSubSeq(left + 1, right), palSubSeq(left, right - 1))
'''return''' L[left][right]
</code>
Функция для построения искомого палиндрома (<tex>left, right</tex> - границы исходной подстроки, <tex>l1=1, l2=L[1][n]</tex>)
<code style = "display: inline-block;">
'''palChars'''(left, right, l1, l2)
'''while''' left <tex>\le</tex> right
'''if''' left = right && L[left][right] = 1
Pal[l1++] = S[left] //массив Char для искомого палиндрома
left++
'''else'''
'''if''' s[left] = s[right]
Pal[l1++] = s[left]
Pal[l2--] = s[right]
left++
right--
'''else'''
'''if''' L[left + 1][right] > L[left][right - 1]
left++
'''else'''
right--
</code>
