Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h>using std::cin;using std::cout;using std::endl;char s_[800000 + 1], s[(800000 + 1) * 2 + 1];/* number of chars to one side of the middle */int p[(800000 + 1) * 2 + 1];int maxr = -1, maxrp;int main() {// scanf("%d", &t);scanf("%s", s_);int l = strlen(s_);memset(s, '#', sizeof(s));for (int i = 0; i < l; ++i)s[i * 2 + 1] = s_[i];long long ans = 0;for (int i = 0; i < 2 * l + 1; ++i) {if (i <= maxr)p[i] = std::min(maxr - i, p[2 * maxrp - i]);while (i - p[i] > 0 && i + p[i] < 2 * l && s[i - p[i] - 1] == s[i + p[i] + 1])++p[i];if (i + p[i] > maxr) {maxr = i + p[i];maxrp = i;}ans += p[i] / 2 + (s[i] == '#' ? 0 : 1);}cout << ans << endl;