Pagini recente » Cod sursa (job #1103134) | Cod sursa (job #1531313) | Cod sursa (job #363627) | Cod sursa (job #110862) | Cod sursa (job #639193)
Cod sursa(job #639193)
#include <fstream>
#include <cstring>
using namespace std;
const char InFile[]="pscpld.in";
const char OutFile[]="pscpld.out";
const int MaxN=1000111;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,st,dr,A[MaxN];
long long sol;
char S[MaxN];
int main()
{
fin>>(S+1);
fin.close();
N=strlen((S+1));
st=dr=1;
for(register int i=1;i<=N;++i)
{
if(i<=dr)
{
A[i]=min(A[st+dr-i],dr-i);
for(st=i-A[i],dr=i+A[i];st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
}
else
{
for(st=dr=i;st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
}
sol+=A[i]+1;
}
st=1;dr=2;
for(register int i=1;i<N;++i)
{
if(S[i]==S[i+1])
{
if(i<=dr)
{
A[i]=min(A[st+dr-i-1],dr-i-1);
for(st=i-A[i],dr=i+1+A[i];st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
}
else
{
for(st=i,dr=i+1;st>1 && dr<N && S[st-1]==S[dr+1];--st,++dr,++A[i]);
}
sol+=A[i]+1;
}
else
{
A[i]=0;
}
}
fout<<sol;
fout.close();
return 0;
}