Pagini recente » Cod sursa (job #1030288) | Cod sursa (job #2918545) | Cod sursa (job #1772006) | Cod sursa (job #2562857) | Cod sursa (job #2802536)
#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;
ifstream in ("pscpld.in");
ofstream out ("pscpld.out");
const long long M1=1000000009;
const long long M2=1000000007;
const long long M3=999996007;
typedef struct haash
{
long long m1;
long long m2;
long long m3;
};
haash add (haash a, haash b)
{
haash res;
res.m1=(a.m1+b.m1)%M1;
res.m2=(a.m2+b.m2)%M2;
res.m3=(a.m3+b.m3)%M3;
return res;
}
haash subt (haash a, haash b)
{
haash res;
res.m1=(a.m1-b.m1+M1)%M1;
res.m2=(a.m2-b.m2+M2)%M2;
res.m3=(a.m3-b.m3+M3)%M3;
return res;
}
haash mult (long long b,haash a)
{
haash res;
res.m1=(a.m1*b)%M1;
res.m2=(a.m2*b)%M2;
res.m3=(a.m3*b)%M3;
return res;
}
haash multh (haash a, haash b)
{
haash res;
res.m1=(a.m1*b.m1)%M1;
res.m2=(a.m2*b.m2)%M2;
res.m3=(a.m3*b.m3)%M3;
return res;
}
bool eq(haash a, haash b)
{
return (a.m1==b.m1&&a.m2==b.m2&&a.m3==b.m3);
}
haash tw27to_2_x (int dexp)
{
haash res;
res.m1=res.m2=res.m3=27;
for(int i=0; i<dexp; i++)
{
res=multh(res,res);
}
return res;
}
int main()
{
string s;
in>>s;
haash fsum [1000010];///forwards sum
haash bsum [1000010];///backwards sum
fsum[0].m1=fsum[0].m2=fsum[0].m3=0;
int i;
haash pows27;
pows27.m1=pows27.m2=pows27.m3=1;
for(i=0; s[i]!='\0'; i++)
{
fsum[i+1]=add(fsum[i],mult(s[i]-'a'+1,pows27));
pows27=mult(27,pows27);
}
int length=i;
pows27.m1=pows27.m2=pows27.m3=1;
for(bsum[i].m1=bsum[i].m2=bsum[i].m3=0; s[i]!='\0'; i++)
{
bsum[i-1]=add(bsum[i],mult(s[i]-'a'+1,pows27));
pows27=mult(27,pows27);
}
long long res=0;
for(i=1; i<=length; i++)
{
int r=0;///impare
for(int step=1<<19; i>=0; i=i>>1)
{
int maybe=r+step;
if(i-maybe-1<0||i+maybe>length)
{
continue;
}
if(i-1>length-i)
{
if(eq(subt(fsum[i-1],fsum[i-1-r]),multh(subt(bsum[i],bsum[i+r]),tw27to_2_x(2*i-length-1))))
{
r=maybe;
}
}
else
{
if(eq(subt(bsum[i],bsum[i+r]),multh(subt(fsum[i-1],fsum[i-1-r]),tw27to_2_x(length+1-2*i))))
{
r=maybe;
}
}
}
res+=r+1;
r=0;
for(int step=1<<19; i>=0; i=i>>1)
{
int maybe=r+step;
if(i-maybe<0||i+maybe>length)
{
continue;
}
if(i>length-i)
{
if(eq(subt(fsum[i],fsum[i-r]),multh(subt(bsum[i],bsum[i+r]),tw27to_2_x(2*i-length))))
{
r=maybe;
}
}
else
{
if(eq(subt(bsum[i],bsum[i+r]),multh(subt(fsum[i],fsum[i-r]),tw27to_2_x(length-2*i))))
{
r=maybe;
}
}
}
res+=r;
}
out<<res;
return 0;
}