Cod sursa(job #1231940)

Utilizator vladrochianVlad Rochian vladrochian Data 21 septembrie 2014 19:11:14
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 1000005;

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

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

int main() {
	fin >> a;
	N = strlen(a);
	N = (N << 1) - 1;
	dp[0] = 1;
	for (int i = 1; i < N; ++i) {
		if (i < extmx + dp[extmx])
			dp[i] = dp[(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;
		if (i + dp[i] > extmx + dp[extmx])
			extmx = i;
	}
	fout << sol << "\n";
	return 0;
}