Cod sursa(job #1840397)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 4 ianuarie 2017 13:36:21
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int n,d[2000003],i,mij,dr;
long long nr;
char s[2000003],gg[2000003];

void psc()
{
    mij=1;
    dr=1;
    for(i=2;i<=n;i++)
    {
        if(i<=dr) d[i]=min(d[2*mij-i],dr-i);
        while(s[i+d[i]+1]==s[i-d[i]-1])
            d[i]++;
        if(i+d[i]>dr)
        {
            mij=i;
            dr=i+d[i];
        }
    }
}

int main()
{
    fin>>(gg+1);
    n=strlen(gg+1);
    nr=n;
    for(i=1;i<=n;i++)
    {
        s[2*i-1]='1';
        s[2*i]=gg[i];
    }
    n=n*2;
    s[0]='2';
    s[n+1]='3';
    psc();
    for(i=1;i<=n;i++)
        if(i%2==1) nr+=(d[i]+1)/2;
         else  nr+=d[i]/2;
    fout << nr;
    return 0;
}