Pagini recente » Cod sursa (job #3179478) | Cod sursa (job #3144496) | Cod sursa (job #3180115) | Cod sursa (job #1958599) | Cod sursa (job #475345)
Cod sursa(job #475345)
#include <fstream>
#include <string>
using namespace std;
const int NMAX=1000005;
int L[2][NMAX],N;
string s;
int main()
{
ifstream fin("pscpld.in");
getline(fin,s);
N=s.length();
int st=0,dr=0,i,j,p,q;
L[0][0]=0;
if (s[0]==s[1]) L[0][0]=1,dr=1;
L[1][0]=1;
for (i=1;i<N;++i)
{
//printf("i=%d st=%d dr=%d\n",i,st,dr);
if (i<dr)
{
j=st+dr-i;
L[0][i]=min(L[0][j-1], j-st);
if (i+L[0][i]==dr)
{
p=i-L[0][i]+1;q=dr;
while (p>0 && q<N-1 && s[p-1]==s[q+1]) ++L[0][i],--p,++q;
}
L[1][i]=min(L[1][j],j-st+1);
if (i+L[1][i]-1==dr)
while ((st=i-L[1][i]+1)>0 && dr<N-1 && s[st-1]==s[dr+1]) ++L[1][i],--st,++dr;
if (q>dr) st=p,dr=q;
}
else
{
L[0][i]=0;
p=i+1;q=i;
while (p>0 && q<N-1 && s[p-1]==s[q+1]) ++L[0][i],--p,++q;
L[1][i]=1;
int _p=i,_q=i;
while (_p>0 && _q<N-1 && s[_p-1]==s[_q+1]) ++L[1][i],--_p,++_q;
if (_q > q) p=_p,q=_q;
if (q > dr) st=p,dr=q;
}
}
long long ans=0;
for (i=0;i<N;++i) ans+=L[1][i];// printf("L[1][%d]=%d\n",i,L[1][i]);
for (i=0;i<N-1;++i) ans+=L[0][i]; //printf("L[0][%d]=%d\n",i,L[0][i]);;
ofstream fout("pscpld.out");
fout<<ans<<"\n";
return 0;
}