Cod sursa(job #1882944)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 17 februarie 2017 16:54:34
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;

ifstream re ("pscpld.in");
ofstream we ("pscpld.out");

const int MAXN = 1000005;
char s[2 * MAXN];
int p[2 * MAXN], n;

int main ()
{
    re >> s;
    n = strlen(s);
    int sum = n;
    for(int i = n  - 1; i >= 0; i--) {
	s[i * 2 + 1] = s[i];
	s[i * 2 + 2] = '#';
    }
    s[0] = '#';
    
    n = n * 2;
    int r = 0;
    int m = 0;
    p[0] = 0;
    p[n] = 0;
    for(int i = 1; i < n; i++) {
	int j;
	//cout << " m = " << m << " r = " << r << " i = " << i << " j = " << j << ' ';
	if(i < r) {
	    j = 2 * m - i;
	    //cout << " jiji:" << j; 
	    if(j >= 0 && i + p[j] < r) {
		p[i] = p[j];
		//cout << "  CAZ 1";
	    } else {
	        j = r - i;
		int aux = 2 * m - r;
		//cout << " gaf:" << aux;
		while((i + j <= n) && (i - j  >= 0) && (s[i + j] == s[i - j])) {
		    j++; //cout << " BAU:" << j;
		}
		j--;
		m = i;
		r = i + j;
		p[i] = j;
		//cout << "  CAZ 2";
	    }
	} else {
	    j = 0;
	    while(i + j <= n && i - j >= 0 && s[i + j] == s[i - j]) {
		j++;
	    }
	    j--;
	    m = i;
	    r = i + j;
	    p[i] = j;
	    ////cout << "  CAZ 3";
	}
	////cout << endl;
	sum += p[i] / 2;
    }
    /*	    
    for(int i = 0; i <= n; i++) {
	we << s[i] << ' ';
    }
    we << endl;
    for(int i = 0; i <= n; i++) {
	we << p[i] << ' ';
    }
    */
    we << sum;

    re.close();
    we.close();

    return 0;
}