Cod sursa(job #2377067)

Utilizator HumikoPostu Alexandru Humiko Data 8 martie 2019 21:25:35
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

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

long long dp[2000005];
string aux;
string s;

int main() {
	ios::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);

	long long ans = 0;

	fin >> aux;
	s += '$';

	for (int i = 0; i < aux.size(); ++i) {
		s += '#';
		s += aux[i];
	}

	s += '#';
	s += '@';
	int n = s.size();
	int c = 0, r = 0;
	for (int i = 2; i < n; ++i) {
		int mirror = 2 * c - i;

		if (i < r) {
			dp[i] = min(1LL*r - i, dp[mirror]);
		}

		while (s[i + dp[i] + 1] == s[i - dp[i] - 1] && dp[i] < n ) {
			dp[i]++;
		}

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

		if (dp[i] + i > r) {
			c = i;
			r = dp[i] + i;
		}
	}

	/*cout << s << '\n';
	for (int i = 0; i < n; ++i) {
		cout << dp[i];
	}*/
	//fout << '\n';
	fout << ans << '\n';
}