Cod sursa(job #2101730)

Utilizator LizaSzabo Liza Liza Data 7 ianuarie 2018 21:30:45
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstring>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMax=2000005;
char A[NMax];
long long Sol ;
int N,r=2,c=1,x,dif,L[NMax];

void Read()
{
   fin>>A;
    N=strlen(A);
    N=2*N+1;
    L[0]=0;
    L[1]=1;
}
void Solve()
{

    for(int i=2;i<=N;i++)
    {
        x=2*c-i;
        dif=r-i;
        if(dif>0)
        {
         L[i]=min(L[x],dif);
        }
         while(((i+L[i])<N && (i-L[i])>0) && (((i+L[i]+1)%2==0) || (A[(i+L[i]+1)/2] == A[(i-L[i]-1)/2])))
        {
            L[i]++;
        }
        if(i+L[i]>r)
        {
            r=i+L[i];
            c=i;
        }
    }

        for(int i=1;i<N;i++)
        {
            if(L[i]%2==1)
                Sol=Sol+L[i]/2+1;
            else
                Sol=Sol+L[i]/2;
        }
        fout<<Sol;

}

int main()
{
    Read();
    Solve();
    return 0;
}