Cod sursa(job #903558)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 martie 2013 22:17:28
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
string s;int p[2000005];
int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    cin>>s;int i;
    string t="+#";
    for(i=0;i<(int)s.length();i++)
        t=t+s.substr(i,1)+"#";
    t+="-";
    int C=0,R=0;
    for(i=1;i<(int)t.size()-1;i++)
    {
        int j=2*C-i;
        if(R>i)
            p[i]=min(R-i,p[j]);
        else
            p[i]=0;
        while(t[i-p[i]-1]==t[i+p[i]+1])
            p[i]++;
        if(i+p[i]>R)
        {
            R=i+p[i];
            C=i;
        }
    }
    long long nr=0;
    for(i=1;i<(int)t.size()-1;i++)
        nr=nr+1LL*(p[i]+1)/2;
    cout<<nr<<endl;
    return 0;
}