Cod sursa(job #1345859)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 17 februarie 2015 21:52:42
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
 
const int nmax= 1000006;
int n, d[2 * nmax], dr, act, j;
string s, aux;
long long rasp;
 
int main(){
	int player_unu=0;

    getline(in, aux);
    s.push_back('0');
	s.push_back('$');
	
	n = 1;
    for(int i = 0; i<(int)aux.size(); i++)
	{
        s.push_back(aux[i]);
        s.push_back('$'); 
		
		n += 2;
    }
 
    for(int i = 1; i<=n; i++)
	{
		if(i<=dr)
		{
            if(i + d[2 * act - i] - 1<dr)
			{
                d[i] = d[2 * act - i];
            }
			else
			{
                j = 1;
                d[i]= dr - i + 1;
 
                while(s[2 * i - dr - j]==s[dr + j])
					j++;

				--j;
                d[i] += j;

				act = i;
				dr = dr + j;
            }
        }
		if(i>dr) 
		{
            j = 1;
            d[i]= 1;
             
            while(s[i - j]==s[i + j])
				j++;

			j--;
            d[i] += j;

			act = i;
			dr = i + j;
        }

		rasp += (d[i] / 2);
    }
 
	out<<rasp<<'\n';

    return player_unu;
}