Contando subseries palindrómicas en O (n)

Question

Dada una cadena (se supone sólo caracteres ingleses) S de longitud n, podemos contar el número de subseries palindrómicas con el siguiente algoritmo:

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 

El código anterior es O(n^2) sin embargo.

Estoy interesado en un algoritmo que resuelve este problema en O(n). Sé con certeza que existe uno ya que he escuchado a varias personas decir que sí, y el problema existe en un sitio local de jueces en línea con un límite superior de 1 000 000 en n, sin embargo, nunca he visto el algoritmo y no puedo parece ser capaz de inventarlo.

Actualización:

La idea general que tengo es para calcular len[i] = length of the longest palindrome centered at the character 2i + 1 y una matriz similar para palíndromos incluso de longitud. Con una buena contabilidad, debería ser posible calcular esto en O(1) para cada personaje, lo que nos permitirá contar una gran cantidad de palíndromos a la vez. Sin embargo, estoy atascado en cómo exactamente calcular esto.

Aceptaré una solución que utiliza O(n) y quizás incluso O(n log n) memoria extra. Creo que esto es imposible sin eso.

Se agradecen todas las buenas ideas o referencias.

Answer 1

El siguiente sitio muestra un algoritmo para calcular la subcadena palindrómica más larga en el tiempo O (n), y lo hace al calcular la subcadena palindrómica más larga en cada centro posible y luego tomar el máximo. Entonces, debería poder modificarlo fácilmente para sus propósitos.

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

EDIT: El primer enlace es un poco inestable una inspección más cercana, por lo que aquí hay otra:

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

Answer 2

Para las cadenas "normales" que debe ser bastante eficiente para mirar a cada personaje como el potencial de "centro" de un palíndromo y luego comprobar si los personajes que rodean realmente construir uno:

# 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] 

Para las cadenas normales de esta debe ser aproximadamente O (n), aunque en el peor de los casos, por ejemplo, si la cadena consta de un solo carácter que se repite una y otra vez, seguirá tomando O (n) vez.

Answer 3

Considérese una cadena S="aaabb".

añadir un carácter de '$' en ambos extremos de la cadena y entre cada dos caracteres consecutivos para cambiar la cadena de S="$a$a$a$b$b$" y aplicar Manacher's algorithm de esta cadena S.

La nueva serie S tiene una longitud 2n + 1 que nos da el tiempo de ejecución de O (2n + 1) que es igual a 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 $ 

Array A es el resultado de Manacher's Algorithm.

Ahora, la suma de A[i]/4 de índice donde '$', de lo contrario (A[i]+1)/4 para cualquier otro personaje de 1 < = i = n < es su respuesta.

Aquí, $ actúa como un centro para las subcadenas palidrómicas de longitud par y la longitud impar se puede calcular normalmente. La respuesta para este caso es:

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