Cod sursa(job #1104300)

Utilizator misinozzz zzz misino Data 10 februarie 2014 17:59:41
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#define N 1000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int c,poz,rez,l,dr,i,lg,sol[N*2];
char s[2*N],s1[N];
inline int cauta(int st,int dr)
{
    int sol=0;
    while(st>=0&&dr<=lg&&s[st]==s[dr])
    --st,++dr,++sol;
    return sol;
}
int main()
{
    f>>s1;
    lg=-1;
    for(i=0;s1[i];++i)
    {
        s[++lg]=s1[i];
        s[++lg]='*';
    }
    c=-1;
    dr=-1;
    for(i=0;i<=lg;++i)
    {
        if(i>dr)
        {
            sol[i]=cauta(i-1,i+1);
            if(sol[i])
            {
                dr=i+sol[i];
                c=i;
            }
        }
        else
        {
            poz=2*c-i;
            l=dr-i;
            if(sol[poz]<l)
            {
                sol[i]=sol[poz];
                continue;
            }
            sol[i]=l+cauta(i-l-1,i+l+1);
            if(sol[i]+i>dr)
            {
                dr=sol[i]+i;
                c=i;
            }
        }
    }
    rez=0;
    for(i=0;i<=lg;++i)
    if(s[i]=='*')
    rez+=(sol[i]+1)/2;
    else
    rez+=sol[i]/2+1;
    g<<rez<<'\n';
    return 0;
}