Cod sursa(job #2040819)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 16 octombrie 2017 16:31:31
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<bits/stdc++.h>
#define Nmax 1000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int p[Nmax];
int pp[Nmax];
string s;
int main()
{
    int center=0,rsh=-1,rad,i;
    long long ans=0;
    f>>s;
    int n=s.size();
    for(i=0;i<n;i++)
    {
        rad=(i>rsh ? 1 : min(p[center+rsh-i],rsh-i)) ;
        while(i+rad<n and i-rad>=0 and s[i+rad]==s[i-rad])
            ++rad;
        p[i]=rad;
        if(i+rad-1>rsh)
        {
            center=i-rad;
            rsh=i+rad-1;
        }
    }
    center=0;
    rsh=-1;
    for(i=0;i<n;i++)
    {
        rad=(i>rsh ? 0 : min(pp[center+rsh-i+1],rsh-i+1))+1;
        while(i+rad-1<n and i-rad>=0 and s[i+rad-1]==s[i-rad])
            ++rad;
        pp[i]=--rad;
        if(i+rad-1 >rsh)
        {
            center=i-rad;
            rsh=i+rad-1;
        }
    }
    for(i=0;i<n;i++)
        ans+=(1LL*(p[i]+pp[i]));
    g<<ans;

    return 0;
}