Cod sursa(job #1281632)

Utilizator armandpredaPreda Armand armandpreda Data 3 decembrie 2014 15:25:18
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

char s[2000005];
int v[2000005],imax,lgmax;
int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    int n,i;
    long long sol=0;
    fin>>s;
    n=strlen(s);
    for(i=n-1;i>=0;--i)
        s[i*2+1]=s[i];
    n=2*n;
    s[0]='$';
    s[n+1]='&';
    for(i=2;i<=n;i+=2)
        s[i]='#';
    v[1]=1;
    imax=1;
    lgmax=1;
    for(i=1;i<=n;++i)
    {
        v[i]=min(imax+lgmax-i,v[2*imax-i]);
        while(s[i-v[i]]==s[i+v[i]])
            v[i]++;
        if(i+v[i]>imax+lgmax)
            imax=i,lgmax=v[i];

    }
    for(i=1;i<=n;++i)
        if(i%2==1)
            sol+=(v[i]+1)/2;
        else
            sol+=v[i]/2;
    fout<<sol;
    return 0;
}