Pagini recente » Istoria paginii runda/simularegrafuri/clasament | Cod sursa (job #2615618) | Cod sursa (job #1932371) | Cod sursa (job #2024341) | Cod sursa (job #2335868)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[1000005];
char s[2000010];
int p[2000010];
int l,P,c,r,simi;
void addHash(){
l=strlen(a);
for(int i=0; i<l; i++){
s[2*i] = '#';
s[2*i+1] = a[i];
}
s[2*l]='#';
P=2*l+1;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",a);
addHash();
long long vmax=0;
for(int i=1; i<P; i++){
simi=c-(i-c);
if(i<=r)///decat cea mai din dreapta parte
p[i]=min(r-i,p[simi]);
while( i+1+p[i]<P && i-1+p[i]>=0 && s[i+1+p[i]]==s[i-1-p[i]]){
p[i]++;
}
if(i+p[i]>r)
{
c=i;
r=i+p[i];
}
vmax=vmax+1LL*(p[i]+1)/2;
}
printf("%d",vmax);
return 0;
}