Cod sursa(job #1962433)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 11 aprilie 2017 19:14:26
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define NMax 1000005
using namespace std;
int C,R,ii,dif,i,lps[2*NMax],N;
long long sum;
char s[NMax];
int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    scanf("%s",&s);
    C=1;
    lps[0]=0;
    lps[1]=1;
    N=strlen(s);
    N=2*N+1;
    for(i=2; i<N; ++i)
    {
        ii=2*C-i;
        dif=R-i;
        lps[i]=0;
        if(dif>0)
            lps[i]=min(dif,lps[ii]);
        while(((i+lps[i])<N&&(i-lps[i])>0)&&(((i+lps[i]+1)%2==0)||(s[(i+lps[i]+1)/2]==s[(i-lps[i]-1)/2])))
            lps[i]++;
        if(i+lps[i]>R)
        {
            C=i;
            R=i+lps[i];
        }
    }
    for(i=1; i<N; i++)
    {
        if(lps[i]%2==0) sum+=lps[i]/2;
        else sum+=lps[i]/2+1;
    }
    printf("%lld\n",sum);
    return 0;
}