Mai intai trebuie sa te autentifici.
Cod sursa(job #2289076)
Utilizator | Data | 24 noiembrie 2018 10:57:52 | |
---|---|---|---|
Problema | PScPld | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.99 kb |
#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]])
{
p[i]+=1;
}
if(i+p[i]>r)
{
r=i+p[i];
c=i;
}
if(p[i]%2==1)
nr+=p[i];
}
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
manacher();
printf("%d",nr);
return 0;
}