Cod sursa(job #1517078)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 3 noiembrie 2015 20:42:20
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
#include<cstring>
using namespace std;
char s[2000010];
int l[2000010];
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
int main(){
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    int n,i,right=0,centre=0;
    long long answer=0;
    gets(s+1);
    n=strlen(s+1);
    for(i=n;i>=1;i--){
        s[2*i-1]=s[i];
        s[2*i]=' ';
    }
    n=2*n;
    s[0]=s[n]=' ';
    for(i=1;i<n;i++){
        if(i<=right)
            l[i]=minim(right-i,l[2*centre-i]);
        while(i-l[i]-1>=0&&i+l[i]+1<=n&&s[i-l[i]-1]==s[i+l[i]+1])
            l[i]++;
        if(i+l[i]>right){
            right=i+l[i];
            centre=i;
        }
        answer=answer+(l[i]+1)/2;
    }
    printf("%lld",answer);
    return 0;
}