Cod sursa(job #1231925)

Utilizator vladrochianVlad Rochian vladrochian Data 21 septembrie 2014 18:53:37
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 1000005;

int N, extmx, sol = 1;
char a[NMAX], dp[NMAX << 1];

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

int main() {
	fin.getline(a, NMAX);
	N = strlen(a);
	N = (N << 1) - 1;
	dp[0] = 1;
	for (int i = 1; i < N; ++i) {
		if (i < extmx + dp[extmx])
			dp[i] = (extmx << 1) - i;
		else
			dp[i] = 1 - (i & 1);
		while (i + dp[i] < N - 1 && i - dp[i] > 0) {
			if (a[(i + dp[i] + 1) >> 1] != a[(i - dp[i] - 1) >> 1])
				break;
			dp[i] += 2;
		}
		sol += (dp[i] + 1) >> 1;
	}
	fout << sol << "\n";
	return 0;
}