Pagini recente » Cod sursa (job #1445535) | Cod sursa (job #35288) | Cod sursa (job #1386237) | Autentificare | Cod sursa (job #3206884)
#include <fstream>
const int NMAX=2000005;
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
void manacher(int [], char*);
char s[NMAX], t[2*NMAX];
int ans[2*NMAX];
signed main()
{
int i;
long long sum=0;
cin>>s;
manacher(ans, s);
for(i=0; t[i]; i++) sum+=(ans[i])/2;
cout<<sum<<'\n';
return 0;
}
void manacher(int v[], char *s)
{
int i, lg=0;
t[lg]='#';
for(i=0; s[i]; i++)
{
t[++lg]=s[i];
t[++lg]='#';
}
int dr=0, st=0, k;
for(i=0; t[i]; i++)
{
if(i>dr) k=1;
else k=min(ans[dr+st-i], dr-i+1);
while(true)
{
if(i-k<0 || !t[i+k]) break;
if(t[i-k]==t[i+k]) k++;
else break;
}
ans[i]=k--;
if(dr<=i+k)
{
dr=i+k;
st=i-k;
}
}
}