algorithm - 最长回文前缀

Question

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

Answer 1

使用 rolling hash .如果 a 是您的字符串，则让 ha[x] 成为 a 中第一个 x 个字符的哈希计算从左到右，让 hr[x] 是从右到左计算的 s 中第一个 x 个字符的散列。您对 hf[i] = hb[i] 的最后位置 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;
}