Pagini recente » Cod sursa (job #2788185) | Cod sursa (job #41882) | Cod sursa (job #1283059) | Cod sursa (job #2760777) | Cod sursa (job #2774376)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const ll NMAX = 2000005;
char c[NMAX],a[NMAX];
ll n,P[NMAX],rasp=0;
ll minim(ll x,ll y){
if(x<y) return x;
return y;
}
void citire(){
fin >> (c+1);
n=strlen(c+1);
for(ll i=1;i<=n;i++){
a[i*2-1]='#';
a[i*2]=c[i];
}
a[n*2+1]='#';
n=2*n+1;
}
void pscpld(){
ll c=0;
for(ll i=1;i<=n;i++){
if(i<=c+P[c]) P[i]=minim(P[2*c-i],c+P[c]-i);
while(a[i+P[i]+1]==a[i-P[i]-1]) P[i]++;
if(i+P[i]>c+P[c]){
c=i;
}
}
}
void solve(){
for(ll i=1;i<=n;i++){
if(i%2==1) rasp+=P[i]/2;
else rasp+=P[i]/2+1;
}
}
void afis(){
fout << rasp;
}
int main()
{
citire();
pscpld();
solve();
afis();
return 0;
}