Cod sursa(job #975593)

Utilizator gbi250Gabriela Moldovan gbi250 Data 20 iulie 2013 20:33:40
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstring>
#include <fstream>
using namespace std;
char str[1000002], s[2000006];
int p[2000006], i, len, n, l, r;
long long nr=1;

void expand(int &l, int &r)
{
    while(s[l-1]==s[r+1] && l>=2 && r<=n-1)
        ++p[i], --l, ++r;
}

void manacher()
{
    len=strlen(str)-1;
    for(i=0;i<=len;++i)
    {
        s[++n]=str[i];
        s[++n]='#';
    }
    l=r=1;
    for(i=2;i<=n;++i)
    {
        if(i<=r)
        {
            p[i]=min(p[r-i+l], r-i);
            if(p[i]==r-i)
            {
                l=i-p[i];
                expand(l, r);
            }
        }
        else
        {
            r=l=i;
            expand(l, r);
        }
        if(i&1)
            nr+=(p[i]+2)>>1;
        else
            nr+=(p[i]+1)>>1;
    }
}

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    fin>>str;
    manacher();
    fout<<nr<<'\n';
    return 0;
}