Cod sursa(job #929539)

Utilizator tudy23Coder Coder tudy23 Data 27 martie 2013 08:44:06
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
using namespace std;
const int N=100100;
char s[N],t[N];
int p[2*N+3];
int k;
long long rez;
void citire()
{
    ifstream f("pscpld.in");
    f.get(s,N);
    f.close();
}
void preproc()
{
    t[0]='$';
    for(int i=0;s[i]!='\0';++i)
        t[++k]='#',t[++k]=s[i];
    t[++k]='#';
    t[++k]='^';
}
void solve()
{
    int c=0,r=0; //centru si limita dreapta
    for(int i=1;i<k-1;++i)
    {
        int i_sim=2*c-i;       //simetric fata de centru
        p[i]=(r>i)?min(r-i,p[i_sim]):0;
        while(t[i+p[i]+1]==t[i-p[i]-1])
            p[i]++;
        if(i+p[i]>r)
        {
            c=i;
            r=i+p[i];
        }
        rez+=((p[i]+1)/2);
    }
}
void afisare()
{
    ofstream h("pscpld.out");
    h<<rez;
    h.close();
}
int main()
{
    citire();
    preproc();
    solve();
    afisare();
    return 0;
}