Подсчет палиндромных подстрок в O (n)

Question

Учитывая строку (допустим только английские символы) S длины n, мы можем подсчитать количество палиндромных подстрок с помощью следующего алгоритма:

for i = 0 to |S| do
    p1 = number of palindromes centered in i (odd length)
    p2 = number of palindromes centered in i and i+1 (even length)

    add p1 + p2 to total number of palindromic substrings of S

Код выше O(n^2).

Меня интересует алгоритм, который решает эту проблему в O(n). Я точно знаю, что он существует, поскольку я слышал, что многие люди говорят, что это так, и проблема существует на местном сайте онлайн-судейства с верхней границей 1 000 000 на n, однако я никогда не видел алгоритм и не может быть в состоянии придумать это.

Обновление:

Основная идея, которую я имею, состоит в том, чтобы вычислить len[i] = length of the longest palindrome centered at the character 2i + 1 и аналогичный массив для палиндромов четной длины. При хорошем ведении бухгалтерии должно быть возможно вычислить это в O(1) для каждого символа, что позволит нам подсчитать много палиндромов одновременно. Однако я застрял на том, как именно это вычислить.

Я приму решение, которое использует O(n) и, возможно, даже O(n log n) дополнительную память. Я думаю, что это невозможно без этого.

Любые хорошие идеи или ссылки приветствуются.

Answer 1

На следующем сайте показан алгоритм для вычисления самой длинной палиндромной подстроки за O (n) времени, и он делает это путем вычисления самой длинной палиндромной подстроки в каждом возможном центре, а затем беря максимум.Таким образом, вы должны иметь возможность легко изменить его для своих целей.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

РЕДАКТИРОВАТЬ: Первая ссылка выглядит немного шатко при ближайшем рассмотрении, поэтому вот еще одна:

http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829

Answer 2

Рассмотрим строку S="aaabb".

Добавьте символ '$' на обоих концах строки и между каждыми двумя последовательными символами, чтобы изменить строку на S="$a$a$a$b$b$" и применить Алгоритм Manacher для этой строки S.

Новая строка S имеет длину 2n + 1, что дает нам время выполнения O (2n + 1), которое совпадает с O (n).

index :  1 2 3 4 5 6 7 8 9 10 11
A     :  1 3 5 7 5 3 1 3 5  3  1
S     :  $ a $ a $ a $ b $  b  $

Массив A является результатом алгоритма Манахера.

Теперь сумма A[i]/4 для индекса, где '$', иначе (A[i]+1)/4 для каждого другого символа из 1 <= i <= n, является вашим ответом. </p>

Здесь $ действует как центр для палидромных подстрок четной длины, и нечетная длина может быть вычислена нормально. Ответ для этого случая:

0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a, a, aaa, a, b, b, aa, aa, bb).

Answer 3

Для «обычных» строк должно быть достаточно эффективно рассматривать каждый символ как потенциальный «центр» палиндрома, а затем проверять, действительно ли окружающие символы строят его:

# check odd palindromes
for center in range(len(ls)):
   # check how many characters to the left and right of |center|
   # build a palindrome
   maxoffs = min(center, len(ls)-center-1)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs]:
      offs += 1
   offs -= 1
   print ls[center-offs : center+offs+1]                                    

# check for even palindromes
for center in range(len(ls)-1):
   maxoffs = min(center, len(ls)-center-2)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]:
      offs += 1
   offs -= 1
   if offs >= 0:
      print ls[center-offs : center+offs+2]

Для нормальных строк это должно быть около O (n), хотя в худшем случае, например, если строка состоит только из одного символа, повторяемого снова и снова, все равно будет принимать O (n ² ) время.