Cod sursa(job #2262533)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 17 octombrie 2018 16:19:39
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 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, rez;
string st;

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 &aux = dp[crt];
		while (s[crt+aux] == s[crt-aux]) {
			++aux;
		}
		--aux;
		if (d < crt + aux) {
			d = crt + aux;
			m = crt;
			p = 1;
		}
		++crt;
	}
	for (int i = 0; i <= n; ++i)
		rez += (dp[i] + 1)/2;
	fo << rez;
	return 0;
}