ti-enxame.com

Contando substratos palíndricos em O(n)

Dada uma string (assuma apenas caracteres em inglês) S de comprimento n, podemos contar o número de substrings palindrômicos com o seguinte 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

O código acima é O(n^2) no entanto.

Estou interessado em um algoritmo que resolve esse problema em O(n). Tenho certeza de que existe uma, como já ouvi várias pessoas dizerem, e o problema existe em um site de juízes on-line local com um limite superior de 1 000 000 Em n, mas eu nunca vi o algoritmo e parece que não consigo apresentá-lo.

Atualização:

A idéia geral que tenho é calcular len[i] = length of the longest palindrome centered at the character 2i + 1 E uma matriz semelhante para palíndromos de comprimento par. Com uma boa contabilidade, deve ser possível calcular isso em O(1) para cada caractere, o que permitirá contar muitos palíndromos de uma só vez. No entanto, estou preso em como exatamente calcular isso.

Aceitarei uma solução que use O(n) e talvez até O(n log n) memória extra. Eu acho que isso é impossível sem ele.

Todas as boas idéias ou referências são apreciadas.

31
IVlad

O site a seguir mostra um algoritmo para calcular a substring palindrômica mais longa em tempo O(n), e faz isso calculando a substring palindromic mais longa em todos os centros possíveis e, em seguida, obtendo o máximo. deve poder modificá-lo facilmente para seus propósitos.

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

EDIT: O primeiro link parece um pouco instável após uma inspeção mais detalhada, então aqui está outro:

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

7
Paul Accisano

Para cadeias "normais", deve ser bastante eficiente olhar para cada personagem como o potencial "centro" de um palíndromo e depois verificar se os caracteres ao redor realmente construíram uma:

# 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 cadeias normais, isso deve ser sobre O (n), embora, na pior das hipóteses, por exemplo, se a cadeia consistir em apenas um caractere repetido várias vezes, ainda será usado O (n2) Tempo.

1
sth

Considere uma string S="aaabb".

Anexar um caractere '$' nas duas extremidades da cadeia e entre dois caracteres consecutivos para alterar a cadeia para S="$a$a$a$b$b$" e aplique algoritmo do Manacher para esta string S.

A nova string S tem comprimento 2n + 1, o que nos dá um tempo de execução de O (2n + 1), que é 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  $

A matriz A é o resultado do algoritmo do Manacher.

Agora, o somatório de A[i]/4 para o índice em que '$', outro (A[i]+1)/4 para todos os outros caracteres de 1 <= i <= n é a sua resposta.

Aqui, $ atua como um centro para os substratos palidroméricos de comprimento par e o comprimento ímpar pode ser calculado normalmente. A resposta para este caso é:

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

1
Aakash Prakash