Cod sursa(job #2366880)

Utilizator LucaSeriSeritan Luca LucaSeri Data 4 martie 2019 22:36:24
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
 
using namespace std;


const int MAXN = 2e6 + 10;

#ifndef BLAT 
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
#endif

int dp[MAXN];
int main() {

	#ifdef BLAT
		freopen("input", "r", stdin);
		#define f cin
		#define g cout
	#endif
	
	ios::sync_with_stdio(false);
	f.tie(0);
	g.tie(0);

	string m;
	f >> m;

	string s = "#";
	for(auto &x : m) s = s + x + '#';

	long long ans = 0;

	for(int i = 0, l = 0, r = -1; i < s.size(); ++i) {
		int k = (i > r) ? 1 : min(r - i, dp[l + r - i]);
		while(i - k >= 0 && i + k < s.size() && s[i-k] == s[i+k]) ++k;

		dp[i] = k--;

		ans += (dp[i])/2;

		if(i + k > r) {
			r = i + k;
			l = i - k;
		}
	}

	g << ans << '\n';
    return 0;
}