Pagini recente » Cod sursa (job #438869) | Cod sursa (job #2410547) | Cod sursa (job #1053371) | Cod sursa (job #2623818) | Cod sursa (job #1973879)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int nmax=1000005;
string s;
int A[nmax],B[nmax];
int i,mx,ind;
long long tot;
int main()
{
ifstream f("pscpld.in");
ofstream g("pscpld.out");
f>>s;
//A[i]-impar
//B[i]-par
for(i=0;i<s.size();i++)
{
mx=A[i];
while(i-mx>=0&&i+mx<s.size()&&s[i-mx]==s[i+mx])
mx++;
mx--;
while(A[i]!=mx+1)
{
ind=i+A[i];
if(min(mx+i-ind,A[i-A[i]])>A[ind])
A[ind]=min(mx+i-ind,A[i-A[i]]);
if(min(i+mx-ind,B[i-A[i]])>B[ind])
B[ind]=min(i+mx-ind,B[i-A[i]]);
A[i]++;
}
A[i]--;
mx=B[i];
while(i-mx+1>=0&&i+mx<s.size()&&s[i-mx+1]==s[i+mx])
mx++;
mx--;
while(B[i]!=mx+1)
{
ind=i+B[i];
if(min(i+mx-ind,A[i-B[i]+1])>A[ind])
A[ind]=min(i+mx-ind,A[i-B[i]]);
if(min(i+mx-ind,B[i-B[i]+1])>B[ind])
B[ind]=min(i+mx-ind,B[i-B[i]+1]);
B[i]++;
}
B[i]--;
if(B[i]==-1) B[i]=0;
tot+=1LL*(A[i]+B[i]+1);
}
g<<tot;
return 0;
}