Cod sursa(job #1046718)

Utilizator andreiiiiPopa Andrei andreiiii Data 3 decembrie 2013 13:23:56
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <string>
#define MIN(a, b) ((a)<(b))?(a):(b)

const int N=2000010;

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

string cit, a;
int p[N];

int main()
{
    int r=0, c=0, i;
    long long sol=0;
    fin>>cit;
    a+='@';
    for(auto x: cit)
    {
        a+='#';
        a+=x;
    }
    a+="#$";
    for(i=1;i<a.size()-1;i++)
    {
        if(r>i) p[i]=MIN(r-i, p[2*c-i]);
        while(i+p[i]+1<a.size()&&i-p[i]-1>=0&&a[i+p[i]+1]==a[i-p[i]-1]) p[i]++;
        if(i+p[i]>r)
        {
            r=i+p[i];
            c=i;
        }
    }
    for(i=1;i<a.size();i++) sol+=(p[i]+1)/2;
    fout<<sol;
}