algorithm - secuencias - Contando subcadenas palindrómicas en O(n)

palindromos

Question

Dada una cadena (supongamos solo caracteres en inglés) S de longitud n , podemos contar el número de subcadenas 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 puedo Parece ser capaz de inventarlo.

Actualizar:

La idea general que tengo es calcular len[i] = length of the longest palindrome centered at the character 2i + 1 y una matriz similar para palíndromos de longitud equitativa. 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 use O(n) y quizás incluso O(n log n) memoria extra. Creo que esto es imposible sin eso.

Cualquier buena idea o referencia es apreciada.

Answer 1

Considere una cadena S="aaabb" .

Agregue un carácter ''$'' en ambos extremos de la cadena y entre cada dos caracteres consecutivos para cambiar la cadena a S="$a$a$a$b$b$" y aplique el algoritmo de Manacher para esta cadena S

La nueva cadena S es de longitud 2n + 1, lo 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  $

La matriz A es el resultado del algoritmo de Manacher.

Ahora, la suma de A[i]/4 para índice donde ''$'' , else (A[i]+1)/4 para cada otro carácter de 1 <= i <= n es su respuesta.

Aquí, $ actúa como un centro para las subcadenas palidrómicas de longitud par y la duración 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).

Answer 2

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/

EDITAR: El primer enlace se ve un poco inestable después de una inspección más cercana, así que aquí hay otro:

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

Answer 3

Para cadenas "normales" debería ser bastante eficiente mirar a cada personaje como el potencial "centro" de un palíndromo y luego verificar si los personajes circundantes realmente construyen 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 cadenas normales esto debería ser aproximadamente O (n), aunque en el peor de los casos, por ejemplo, si la cadena consta de un solo carácter repetido una y otra vez, todavía tomará O (n ² ) tiempo.