Pagini recente » Borderou de evaluare (job #2899106) | Borderou de evaluare (job #276721) | Borderou de evaluare (job #2416077) | Borderou de evaluare (job #1376656) | Cod sursa (job #1969572)
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for (int i = 0; i < a; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define FOREACH(it,x) for (auto it: (x))
#define pb push_back
#define SZ(x) ((int)(x).size())
char text[1000005];
int p[2][1000005];
int n;
void Manacher()
{
int l = -1,r = -1;;
REP(i,n) { /// odd length
if (r < i) p[1][i] = 1;
else p[1][i] = min(r - i + 1, p[1][l+r-i]);
int L = i - p[1][i] + 1, R = i + p[1][i] - 1;
while (L-1 >= 0 && R+1 < n && text[L-1] == text[R+1]) L--,R++,p[1][i]++;
if (R > r) r = R,l = L;
}
l = -1,r = -1;
REP(i,n) { /// even length
if (r < i) p[0][i] = 0;
else p[0][i] = min(r - i + 1, p[0][l+r-i+1]);
int L = i - p[0][i], R = i + p[0][i] - 1;
while (L-1 >= 0 && R+1 < n && text[L-1] == text[R+1]) L--,R++,p[0][i]++;
if (R > r) r = R,l = L;
}
}
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> text; n = strlen(text);
Manacher();
long long sol = 0;
REP(i,n) sol += p[1][i] + p[0][i];
fout << sol;
}