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