Самый длинный префикс палиндрома

Question

Как найти самый длинный префикс палиндрома строки в O (n)?

Answer 1

решения для более общей проблемы, а не префикс, но подстрока, в О (п):

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

Второй результат на Google для "длинной палиндромности префикса" ....

Или решение с помощью суффиксов деревьев:

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

Answer 2

Используйте 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; 
}