Алгоритм Манакера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 
  <font color=green>// <tex>s</tex> {{---}} исходная строка</font>
 
  <font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font>
 
  <font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font>
'''function''' <tex>\mathtt{calculate}():</tex>
+
  '''for''' i = 1 '''to''' n
     '''for''' <tex>i \in 1...|s|</tex>
+
    d1[i] = 1
 +
    '''while''' i - d1[i] > 0 '''and''' i + d1[i] <= n '''and''' s[i - d1[i]] == s[i + d1[i]]
 +
      d1[i]++
 +
    d2[i] = 0
 +
     '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]]
 +
      d2[i]++

Версия 11:38, 10 марта 2016

Задача:
Пусть дана строка [math]s[/math]. Требуется найти [math]d1[i][/math] - длина наибольшего палиндрома нечетной длины с центром в позиции [math]i[/math] и [math]d2[i][/math]- аналогично для палиндромов четной длины для всех [math]i[/math] от 1 до [math]|s|[/math].


Наивный алгоритм

Идея

Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции [math]i[/math], будем на каждом шаге увеличивать длину палиндрома с центром в [math]i[/math] и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за [math]O(n^2)[/math]

Псевдокод

// [math]s[/math] — исходная строка
// [math]d1, d2[/math] — массивы для записи ответа
 for i = 1 to n
   d1[i] = 1
   while i - d1[i] > 0 and i + d1[i] <= n and s[i - d1[i]] == s[i + d1[i]]
     d1[i]++
   d2[i] = 0
   while i - d2[i] - 1 > 0 and i + d2[i] <= n and s[i - d2[i] - 1] == s[i + d2[i]]
     d2[i]++