Pagini recente » Cod sursa (job #2221967) | Cod sursa (job #1507877) | Cod sursa (job #1856873) | Cod sursa (job #2096847) | Cod sursa (job #1240674)
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>
using namespace std;
#define dbg(x) (cout<<#x<<" = "<<(x)<<'\n')
const string problemName = "pscpld";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
typedef long long int lld;
typedef pair<int, int> PII;
const int INF = (1LL << 31) - 1;
const lld LINF = (1LL << 62) - 1;
const int NMAX = 1000000 + 5;
int N, M;
lld sol;
char S[NMAX];
char A[2 * NMAX];
int P[2 * NMAX];
void manacher() {
int i, j, right, center, d;
N = strlen(S + 1);
for(i = 1; i <= N; i++) {
A[++M] = S[i];
A[++M] = '$';
}
A[0] = '#';
A[M] = '*';
M--;
right = center = 0;
for(i = 1; i <= M; i++) {
d = 0;
if(i <= right) {
j = 2 * center - i;
d = min(right - i, P[j]);
}
while(A[i - d] == A[i + d] && (i - d))
d++;
if(!(i % 2))
d--;
P[i] = d;
if(i + d > right) {
center = i;
right = i + d;
}
}
}
int main() {
int i;
#ifndef ONLINE_JUDGE
freopen(inputFile.c_str(), "r", stdin);
freopen(outputFile.c_str(), "w", stdout);
#endif
scanf("%s", S + 1);
manacher();
for(i = 1; i <= M; i++)
sol += (P[i] + 1LL) / 2;
printf("%lld\n", sol);
return 0;
}