Pagini recente » Cod sursa (job #306174) | Cod sursa (job #2141215) | Cod sursa (job #1563730) | Cod sursa (job #1752745) | Cod sursa (job #755781)
Cod sursa(job #755781)
#include<fstream>
using namespace std;
char v[1000100],s[2000100];
int n,Lg[2000100];
long long sol;
int main()
{
int i,st,dr,poz;
ifstream fin("pscpld.in");
fin>>v;
fin.close();
n=0;
s[++n]='*';
for(i=0;v[i]!=0;i++)
{
s[++n]=v[i];
s[++n]='*';
}
st=1;
dr=3;
Lg[2]=1;
for(i=3;i<=n;i++)
{
if(i>dr)
{
st=dr=i;
while(st>1 && dr<n && s[st-1]==s[dr+1])
{
Lg[i]++;
st--;
dr++;
}
}
else
{
poz=st+(dr-i);
if(i+Lg[poz]<dr)
Lg[i]=Lg[poz];
else
{
Lg[i]=dr-i;
st=i-Lg[i];
dr=i+Lg[i];
while(st>1 && dr<n && s[st-1]==s[dr+1])
{
Lg[i]++;
st--;
dr++;
}
}
}
}
for(i=1;i<=n;i++)
sol+=(long long)((Lg[i]+1)/2);
ofstream fout("pscpld.out");
fout<<sol<<"\n";
fout.close();
return 0;
}