Longest palindrome prefix

Question

How to find the longest palindrome prefix of a string in O(n)?

Answer 1

Use a rolling hash. If a is your string, let ha[x] be the hash of the first x chars in a computed from left to right and let hr[x] be the hash of the first x characters in s computed from right to left. You're interested in the last position i for which hf[i] = hb[i].

Code in C (use two hashes for each direction to avoid false positives):

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