Pagini recente » Cod sursa (job #1444143) | Cod sursa (job #2277146) | Cod sursa (job #162130) | Cod sursa (job #2298688) | Cod sursa (job #2220039)
#include <iostream>
#include <fstream>
#define MAX 1000010
using namespace std;
int n,ansf,sz;
int ansi[MAX],ansp[MAX];
string s;
void veri(int ind){
for(int j1=ind-ansi[ind],j2=ind+ansi[ind];j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++)
ansi[ind]++;
}
void verp(int ind){
for(int j1=ind-ansi[ind],j2=ind+ansi[ind]+1;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++)
ansi[ind]++;
}
int main()
{
ifstream f ("pscpld.in");
ofstream g ("pscpld.out");
f>>s;n=s.size();s="!"+s;
ansi[1]=1;
for(int i=2;i<=n;i++){
if(ansi[i])continue;
sz=0;
for(int j1=i,j2=i;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++,sz++);
//cout<<sz<<" ";
ansi[i]=sz;
for(int j=1;j<=sz-1;j++)
ansi[i+j]=min(ansi[i-j],sz-j),
veri(i+j);
}
//cout<<'\n'; for(int i=1;i<=n;i++)cout<<ansi[i]<<" ";
ansp[1]=((s[1]==s[2])?1:0);
for(int i=2;i<=n;i++){
if(ansp[i])continue;
sz=0;
for(int j1=i,j2=i+1;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++,sz++);
ansp[i]=sz;
for(int j=1;j<=sz-1;j++)
ansi[i+j+1]=min(ansi[i-j],sz-j),
veri(i+j+1);
}
//cout<<'\n'; for(int i=1;i<=n;i++)cout<<ansp[i]<<" ";
for(int i=1;i<=n;i++)
ansf+=ansi[i]+ansp[i];
g<<ansf<<'\n';
f.close();
g.close();
return 0;
}