Cod sursa(job #2040809)

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

    return 0;
}