Хотел бы поделиться опытом изучения алгоритма Манакера. При запросе "Алгоритм Манакера" в гугле и яндексе первыми выходят 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...))