conteggio sottostringhe palindromi a O (n)

Question

data una stringa (assumere solo caratteri inglesi) S di lunghezza n, possiamo contare il numero di sottostringhe palindromiche con il seguente 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 

Il codice sopra è O(n^2) però.

Sono interessato a un algoritmo che risolve questo problema in O(n). So per certo che esiste come ho sentito dire da più persone, e il problema esiste in un sito locale di giudici online con un limite superiore di 1 000 000 su n, tuttavia non ho mai visto l'algoritmo e non posso sembra di essere in grado di venire con esso.

Aggiornamento:

L'idea generale che ho è quello di calcolare len[i] = length of the longest palindrome centered at the character 2i + 1 e un allineamento simile per palindromi anche di lunghezza. Con una buona contabilità, dovrebbe essere possibile calcolare questo in O(1) per ogni personaggio, che ci permetterà di contare un sacco di palindromi tutti in una volta. Sono bloccato su come calcolare esattamente questo comunque.

Accetterò una soluzione che utilizza O(n) e forse anche la memoria aggiuntiva O(n log n). Penso che sia impossibile senza di esso.

Tutte le buone idee o referenze sono apprezzate.

Answer 1

Il seguente sito mostra un algoritmo per il calcolo della sottostringa palindromica più lunga nel tempo O (n), e lo fa calcolando la sottostringa palindromica più lunga in ogni centro possibile e quindi prendendo il massimo. Quindi, dovresti essere in grado di modificarlo facilmente per i tuoi scopi.

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

EDIT: Il primo collegamento sembra un po 'traballante una più accurata analisi, quindi ecco un altro:

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

Answer 2

Per le stringhe "normali" dovrebbe essere piuttosto efficace per guardare ogni personaggio come il potenziale "centro" di un palindromo e quindi controllare se i personaggi che circondano effettivamente costruire 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] 

Per le stringhe normali questo dovrebbe essere di circa O (n), anche se nel peggiore dei casi, ad esempio se la stringa è composta da un solo carattere ripetuto più volte, sarà comunque necessario O (n).

Answer 3

consideri una stringa S="aaabb".

aggiungere un carattere '$' ad entrambe le estremità della stringa e tra ogni due caratteri consecutivi per modificare la stringa da applicare S="$a$a$a$b$b$" e Manacher's algorithm per questa stringa S.

La nuova stringa S è di lunghezza 2n + 1 che ci dà tempo di esecuzione di O (2n + 1) che è uguale 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 $ 

L'array A è il risultato dell'algoritmo di Manacher.

Ora, la somma dei A[i]/4 per l'indice in cui '$', altrimenti (A[i]+1)/4 per ogni altro personaggio dal 1 < = i < = n è la vostra risposta.

Qui, $ funge da centro per le sottostrutture palidromiche di lunghezza pari e la lunghezza dispari può essere calcolata normalmente. La risposta per questo caso è:

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