Cod sursa(job #1532840)

Utilizator SilviuIIon Silviu SilviuI Data 21 noiembrie 2015 17:41:29
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#define nmax 1000010
using namespace std;
int n,i,j,pr,ul,l[2*nmax];
char s[nmax],p[2*nmax];
inline int min(int a,int b) { if (a<b) return a; else return b; }
int main() {
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(s+1); n=1; p[1]='/';
for (i=1;s[i];i++) {
    n++; p[n]=s[i]; n++; p[n]='/';
}
ul=1; pr=1; l[1]=1; n++; p[n+1]='/';
for (i=1;i<=n;i++) {
    if (ul>i) l[i]=min(l[2*pr-i],ul-i); else l[i]=1;
    while (p[i-l[i]]==p[i+l[i]] && i-l[i]>=1 && i+l[i]<=n) l[i]++;
    if (i+l[i]>ul) {
        ul=i+l[i];
        pr=i;
    }
}
int nrsol=0;
for (i=1;i<n;i++) nrsol+=(l[i]/2);
printf("%d",nrsol);
return 0;
}