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

Учитывая строку (предположим только английские символы) 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 on n, однако я никогда не видел алгоритм и, похоже, не в состоянии это сделать.

Update:

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

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

Любые хорошие идеи или ссылки оценены.

Ответы

Ответ 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

Ответ 2

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

# 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 ²).

Ответ 3

Рассмотрим строку 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 для индекса, где '$', else (A[i]+1)/4 для каждого другого символа из 1 <= я <= n - ваш ответ.

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

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