Cod sursa(job #1920307)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 9 martie 2017 23:33:33
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<bits/stdc++.h>
#define tip long long

using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int N,C,l,r,i,mirror,R,n,p[2000010];
tip sol;
char s[2000010],t[2000010];
int main()
{
    f>>s;n=strlen(s);t[0]=' ';
    for(i=0;i<n;i++)
    {
        t[++N]=s[i];
        p[N]=1;
        t[++N]=' ';
    }
    for(i=1;i<N;i++)
    {
        mirror=2*C-i;
        if(i<=R)
            p[i]=min(p[mirror],R-i+1);
        l=i-p[i]+1;r=i+p[i]-1;
        while(l-2>=1&&r+2<=N&&t[l-2]==t[r+2])
        {
            l-=2;r+=2;
            p[i]+=2;
        }
        if(r>R){R=r;C=i;}
        sol+=(p[i]+1)/2;
    }
    g<<sol<<'\n';
    return 0;
}