Pagini recente » Cod sursa (job #200146) | Cod sursa (job #1735599) | Cod sursa (job #476054) | Cod sursa (job #2647864) | Cod sursa (job #1673491)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<bitset>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int const NMax = 1000005;
int L[2*NMax];
char A[NMax], aux[NMax];
int n, dr, center;
long long sol;
void Read()
{
A[0] = '*';
f.getline(aux, 1000005);
strcat(A, aux);
n = strlen(A) - 1;
}
void Solve()
{
int i, mid, low, up, j;
for(i=1; i<=2*n-1; i++){
if(dr > i+1){
if(i % 2){
mid = i/2 + 1;
L[i] = min(L[2*center - i], dr - i);
for(j = L[i]/2 + 1; A[mid + j] == A[mid - j]; j++)
L[i] += 2;
}
else{
low = i/2;
up = i/2 + 1;
L[i] = min(L[2*center - i], dr - i);
for(j = L[i]/2; A[low - j] == A[up + j]; j++)
L[i] += 2;
}
if(i + L[i] > dr){
dr = i + L[i];
center = i;
}
}
else{
if(i % 2){
mid = i/2 + 1;
L[i] = 1;
for(j=1; A[mid + j] == A[mid - j]; j++)
L[i] += 2;
}
else{
low = i/2;
up = i/2 + 1;
for(j=0; A[low - j] == A[up + j]; j++)
L[i] += 2;
}
dr = i + L[i];
center = i;
}
sol += (L[i]+1)/2;
}
g<<sol<<"\n";
}
int main()
{
Read();
Solve();
return 0;
}