Cod sursa(job #2545842)

Utilizator adiaioanaAdia R. adiaioana Data 13 februarie 2020 16:31:48
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string sir,a;
int c,dr,ex[1000100], ans, lg;
int main()
{
    cin>>sir;
    a+='#';
    for(int i=0; i<sir.size(); ++i)
    {
        a+=sir[i];
        a+='#';
    }
    ex[0]=1;
    c=0; dr=0;
    for(int i=1; i<a.size(); ++i)
    {
        lg=1;
        if(i<=dr)
            lg=min(ex[2*c-i],dr-i+1);
        while(i>=lg && i+lg<a.size() && a[i-lg]==a[i+lg])
            ++lg;
        if(i+lg-1>dr)
            dr=i+lg-1, c=i;
        ex[i]=lg;
        ans+=ex[i]/2;
    }
    cout<<ans<<'\n';
    return 0;
}