Cod sursa(job #1880184)

Utilizator dumitrescugeorgeGeorge Dumitrescu dumitrescugeorge Data 15 februarie 2017 16:41:16
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[1000010],t[200020];
int lps[2000100],n;
void citire()
{
    fgets(s,2000000,stdin);
    n=strlen(s);
    for(int i=0;i<n;i++)
    {
        t[2*i+1]=s[i];
        t[2*i]='#';
    }
}
void manacher()
{
    int c=0,dr=0;
    lps[0]=0;
    lps[1]=1;
    for(int i=2;i<=2*n;i++)
    {
        int ii=c+(c-i);
        if(i<dr)
        {
            if(dr-i<lps[ii])
                lps[i]=dr-i;
            else
                lps[i]=lps[ii];
        }
        else
            lps[i]=0;
        while((i-lps[i]-1)>=0&&(i+lps[i]+1)<=2*n+1&&t[i-lps[i]-1]==t[i+lps[i]+1])
            lps[i]++;
        if(lps[i]+i>dr)
    {
        dr=i+lps[i];
        c=i;
    }
    }
    int S=0;
    for(int i=1;i<=2*n-1;i++)
        {
            if(lps[i]%2==0)
                S+=lps[i]/2;
            else
                S+=lps[i]/2+1;
        }
    printf("%d",S);
}
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    citire();
    manacher();
    //cout << "Hello world!" << endl;
    return 0;
}