Cod sursa(job #752820)

Utilizator BoSs_De_BosSSeFu SeFiLoR BoSs_De_BosS Data 29 mai 2012 17:52:39
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

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

const int N = 2000100;

char a[N], s[N];
int p[N], n, poz = 1, l = 1;
long long nr = 1;

inline int min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	int i;
	
	in.getline(a, N);
	
	n = strlen(a);
	
	for(i = 0; i!=n; ++i) {
		s[2*i + 1] = a[i];
		s[2*i] = ' ';
	}
	n = 2*n - 1;
	p[0] = p[1] = 1;
	
	for(i = 2; i<=n; ++i) {
		p[i] = 1;
		
		if(poz + l - 1 > i)
			p[i] = min(poz + l - i, p[2 * poz - i]);
		
		while(i - p[i] && s[i - p[i]] == s[i + p[i]])
			++p[i];
		
		if(i & 1)
			nr += (p[i] + 1)>>1;
		else
			nr += p[i]>>1;
		
		if(s[i] + i > poz + l) {
			poz = i;
			l = p[i];
		}
	}
	
	out << nr << "\n";
	
	return 0;
}