最长的回文前缀

Question

如何在O(n)中找到字符串的最长回文前缀？

Answer 1

使用滚动哈希.如果a是你的字符串,那么让我们从左到右计算ha[x]第一个x字符的哈希值,a让它hr[x]成为从右到左计算的第一个x字符的哈希值s.你感兴趣的最后一个位置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;
}

Answer 2

更一般问题的解决方案，不是前缀而是子字符串，时间复杂度为 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/