Cod sursa(job #2262542)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 17 octombrie 2018 16:26:26
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#define DM 2000005
#include <fstream>
using namespace std;

ifstream fi ("pscpld.in");
ofstream fo ("pscpld.out");
bool p;
char s[DM];
int dp[DM], n, m, d, crt;
long long rez;
string st;

bool ok(int a, int b) {
	return a + b <= n && a - b >= 0;
}

int main() {
	fi >> st;
	for (int i = 0; i < st.size(); ++i) {
		s[2*i] = '*';
		s[2*i+1] = st[i];
	}
	n = 2*st.size();
	s[2*st.size()] = '*';
	m = d = crt = 1;
	p = 0;
	while (crt < n) {
		if (crt > d)
			p = 0;
		dp[crt] = (p) ? min(dp[2*m-crt], d - crt):0;
		int &a = dp[crt];
		while (ok(crt, a) && s[crt+a] == s[crt-a]) {
			++a;
		}
		--a;
		if (d < crt + a) {
			d = crt + a;
			m = crt;
			p = 1;
		}
		++crt;
	}
	for (int i = 0; i <= n; ++i) 
		rez += 1LL*(dp[i] + 1)/2;
	fo << rez;
	return 0;
}