Хотел бы поделиться опытом изучения алгоритма Манакера. При запросе "Алгоритм Манакера" в гугле и яндексе первыми выходят 2 статьи
1. Викиконспекты
2. e-maxx

Описан алгоритм понятно, но вот реализации в обеих статьях не самые хорошие. Если на викиконспектах алгоритм рабочий, то на e-maxx он вообще падает на тесте abacabadabacaba(вроде это уже всем известный факт)
Теперь про реализацию с викиконспектов. Так как моя реализация алгоритма получала WA6, я решил посмотреть(переписать) решение с викиконспектов. Да, 6 тест был пройден успешно, но я получил TL на 7 тесте. Даже после некоторых оптимизаций из TL7 я так и не вылез.

В итоге мои поиски закончились этим

ll Manaker(std::string &a) {  
    int n = int(a.length());  
    int k = 2 * n, mx = -1, id = 0;  
    std::vector<int> d(k);  
    for (int i = 0; i < k; i++) {  
        int i0 = i >> 1, i1 = (i + 1) >> 1;  
        d[i] = mx > i1 ? std::min(mx - i1, d[2 * id - i]) : 0;  
        if (mx <= i1 || mx - i1 <= d[2 * id - i])  
            while (i0 - d[i] >= 0 && i1 + d[i] < n && a[i0 - d[i]] == a[i1 + d[i]])  
                d[i]++;  
        if (i1 + d[i] > mx) {  
            mx = i1 + d[i];  
            id = i;  
        }  
    }  
    ll ans = 0;  
    for (int i : d)  
        ans += i;  
    return ans;  
}     

Тут зашло быстрее, чем a + b на питоне(на acmp не самый точный счетчик времени:D)

Мораль : исправьте уже баг на емаксе добавлено: 23 Aug 2008 21:00 редактировано: 5 Apr 2012 23:14 уже 2019...))