Cod sursa(job #2026971)

Utilizator refugiatBoni Daniel Stefan refugiat Data 25 septembrie 2017 14:14:07
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream si("pscpld.in");
ofstream so("pscpld.out");
char a[2000005];
char t[2000005];
int lg[2000005];
void manacher(int n)
{
    int r=-1,c=0,rad;
    for(int i=0;i<n;++i)
    {
        if(i<=r)
            rad=min(lg[2*c-i],r-i)+1;
        else
            rad=0;
        while(i-rad>=0&&i+rad<n&&a[i-rad]==a[i+rad])
            ++rad;
        lg[i]=rad-1;
        if(i+lg[i]-1>r)
        {
            c=i;
            r=i+lg[i]-1;
        }
    }
}
int main()
{
    si>>t;
    int n;
    n=strlen(t);
    for(int i=0;i<=n;++i)
    {
        a[i*2]='#';
        a[i*2+1]=t[i];
    }
    n=n*2+1;
    manacher(n);
    long long rasp=0;
    for(int i=0;i<n;++i)
    {
        rasp+=(1LL*(lg[i]+1))/2;
    }
    so<<rasp;
    return 0;
}