Cod sursa(job #894233)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 26 februarie 2013 20:19:51
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
#include<algorithm>
#define n_max 9999998
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char S[n_max];
 
int Lung[n_max];
 
int N;
 
long long sol;
 
 
void citeste()
{
     
    while (fin >> S[2 * N + 1])
        N ++;
     
    fin.close();
}
 
 
 
void rezolva()
{
    int idx = 1;
     
    for (int i=1; i<2*N; ++i)
    {
        if (idx + Lung[idx] - 1 < i)
            Lung[i] = i&1;
        else
            Lung[i] = min(Lung[idx - (i - idx)], idx + Lung[idx] - i );
 
        int j = Lung[i] + 1;
         
        while (i - j >= 1 && i + j < 2*N && S[i-j] == S[i+j])
            j+=2;
        j -= 2;
         
        Lung[i] = j + 1;
         
        if ( i + Lung[i] > idx + Lung[idx])
            idx = i;
sol += (Lung[i] + 1) / 2;
    }
}
 
 
 
void afiseaza()
{
     
    fout<<sol<<'\n';
     
    fout.close();
}
 
 
int main(void)
{
    citeste();
    rezolva();
    afiseaza();
     
    return 0;
}