algorithm - 最长回文前缀

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

最佳答案

使用rolling hash。如果您的字符串是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;
}