Pagini recente » Cod sursa (job #3157425) | Cod sursa (job #2264734) | Cod sursa (job #2975964) | Cod sursa (job #3252225) | Cod sursa (job #3272648)
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int base=31,mod=1e9+7,Nmax=1e6+5;
int pw[Nmax],inv_pw[Nmax];
int hsh[Nmax],rev[Nmax];
int n;
int power(int a,int b)
{
int sol=1;
while(b)
{
if(b%2==1) sol=sol*a%mod;
a=a*a%mod;
b=b/2;
}
return sol;
}
void init()
{
pw[0]=1;
inv_pw[0]=1;
for(int i=1;i<=n;i++)
{
pw[i]=pw[i-1]*base%mod;
///cout<<i<<' '<<pw[i]<<'\n';
inv_pw[i]=inv_pw[i-1]*power(base,mod-2)%mod;
}
}
int calch(int l,int r)
{
if(l>r) return 0;
return (hsh[r]+mod-hsh[l-1])%mod*inv_pw[l]%mod;
}
int calcr(int l,int r)
{
if(l>r) return 0;
return (rev[l]+mod-rev[r+1])%mod*inv_pw[n-r-1]%mod;
}
signed main()
{
string s;
fin>>s;
n=s.size();
init();
for(int i=0;i<n;i++)
{
if(i>0) hsh[i]=(hsh[i-1]+pw[i]*(s[i]-'a'+1)%mod)%mod;
else hsh[i]=s[i]-'a'+1;
}
for(int i=n-1;i>=0;i--)
{
rev[i]=(rev[i+1]+pw[n-i-1]*(s[i]-'a'+1)%mod)%mod;
///cout<<i<<' '<<rev[i]<<'\n';
}
int sol=0;
for(int i=0;i<n;i++)
{
///impare
int l=0,r=min(i,n-i-1);
int len=0;
while(l<=r)
{
int mid=(l+r)/2;
int sumr=calch(i+1,i+mid);
int suml=calcr(i-mid,i-1);
///cout<<l<<' '<<r<<' '<<i<<' '<<mid<<' '<<sumr<<' '<<suml<<'\n';
if(sumr==suml)
{
len=mid;
l=mid+1;
}
else r=mid-1;
}
///cout<<i<<' '<<len<<'\n';
sol+=len+1;
///pare
if(i==0 || s[i]!=s[i-1]) continue;
l=0,r=min(i-1,n-i-1);
len=0;
while(l<=r)
{
int mid=(l+r)/2;
int sumr=calch(i+1,i+mid);
int suml=calcr(i-1-mid,i-2);
if(sumr==suml)
{
len=mid;
l=r+1;
}
else r=l-1;
}
///cout<<i<<' '<<len<<' '<<"pare"<<'\n';
sol+=len+1;
}
fout<<sol<<'\n';
return 0;
}