Pagini recente » Cod sursa (job #2058987) | Cod sursa (job #246969) | Cod sursa (job #1680438) | Cod sursa (job #2181179) | Cod sursa (job #2289084)
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
char s[3000000];
int n, c, r; ///n=strlen c= centrul palindromului r=raza
void citire()
{
char c1;
scanf("%c", &c1);
while(c1<='z' && c1>='a')
{
s[n++]='#';
s[n++]=c1;
scanf("%c", &c1);
}
s[n++]='#';
}
int p[3000000]={0};///sirul in care retii palindrom
int nr;
void manacher()
{
int c=0;
int r=0;
for(int i=0; i<n; i++)
{
int ok=0;
int simi=c-(i-c);
p[i]=0;
//if(r>i)
// p[i]=min(r-1,p[simi]);
while(s[i+1+p[i]]==s[i-1-p[i]])
{
if(s[i+1+p[i]]=='#')
nr++;
p[i]+=1;
}
if(i+p[i]>r)
{
r=i+p[i];
c=i;
}
}
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
manacher();
printf("%d",nr);
return 0;
}