Cod sursa(job #1881618)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 16 februarie 2017 17:00:36
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[1000001];

int LPS[2000002];

int c, r, n;

long long int k;

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",s);

    n=2*strlen(s)+1;


    LPS[0]=0;
    LPS[1]=1;
    c=1;
    r=2;

    for(int i=2;i<=n;i++)
    {
        int mirror = 2*c - i;
        bool expand = 0;

        if(r<=i)
        {
            LPS[i]=0;
            expand = 1;
        }
        else
        {
            if(LPS[mirror] < r-i)
            {
                LPS[i]=LPS[mirror];
            }
            else
            {
                LPS[i] = min(LPS[mirror],r-i);
                expand = 1;
            }
        }

        if(expand)
        {
            while(i-LPS[i]>0  && i+LPS[i]<n)
            {
                if((i-LPS[i]-1)%2==0)
                    LPS[i]++;
                else
                {
                    if(s[(i-LPS[i]-1)/2]==s[(i+LPS[i]+1)/2])
                        LPS[i]++;
                    else break;
                }
            }

            if(i+LPS[i] > r)
            {
                r = i+LPS[i];
                c=i;
            }
        }
    }


    for(int i=0;i<n;i++)
    {
        if(LPS[i]%2==0)
            k+=LPS[i]/2;
        else k+=LPS[i]/2+1;
    }

    printf("%lld",k);

    return 0;
}