Le plus long préfixe palindrome

Question

Comment trouver le plus long préfixe de palindrome d'une chaîne dans O (n)?

Answer 1

Solution pour un problème plus général, le préfixe mais pas sous-chaîne, en O (n):

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

second résultat sur Google pour "le plus long préfixe palindrome" ....

Ou

solution en utilisant le suffixe arbres:

http://www.allisons.org/ll/AlgDS/Tree/Suffix/

Answer 2

Utilisez un rolling hash. Si a est votre chaîne, laissez ha[x] être le hachage des premiers caractères x dans a calculé de gauche à droite et laissez hr[x] être le hachage des premiers caractères x dans s calculé de droite à gauche. Vous êtes intéressé par la dernière position i pour laquelle hf[i] = hb[i].

code en C (utiliser deux hash pour chaque direction afin d'éviter les faux positifs):

int match = n - 1; 

int ha1 = 0, ha2 = 0, hr1 = 0, hr2 = 0; 
int m1 = 1, m2 = 1; 
for (int i = 0; a[i]; ++i) 
{ 
    ha1 = (ha1 + m1*a[i]) % mod1; 
    ha2 = (ha2 + m2*a[i]) % mod2; 

    hr1 = (a[i] + base1*hr1) % mod1; 
    hr2 = (a[i] + base2*hr2) % mod2; 

    m1 *= base1, m1 %= mod1; 
    m2 *= base2, m2 %= mod2; 

    if (ha1 == hr1 && ha2 == hr2) 
     match = i; 
}