最长的回文前缀

Question

如何找到O（n）中字符串的最长回文前缀？

Answer 1

解决方案更普遍的问题，而不是前缀，而子串，在O（N）：

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

在谷歌第二个结果为 “最长回文前缀” ......

或使用的解决方案后缀树：

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

Answer 2

使用rolling hash。如果a是您的字符串，则让ha[x]成为从左到右计算的a中第一个x个字符的散列，并且让hr[x]成为s中从头到尾计算的第一个x个字符的散列。您对i的最后位置感兴趣，其中hf[i] = hb[i]。用C

代码（使用两个散列每个方向，以避免假阳性）：

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; 
}