Cod sursa(job #2999841)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 martie 2023 16:39:21
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e6;

string s;
int pal[2 * NMAX + 1];

int main() {
	char ch;
	while(fin >> ch) {
		s.push_back('$');
		s.push_back(ch);
	}
	s.push_back('$');

	for(int i = 0, st = 0, dr = 0; i < (int) s.size(); i++) {
		if(i < dr) {
			pal[i] = min(dr - i + 1, pal[st + dr - i]);
		}

		while(i - pal[i] >= 0 && i + pal[i] < (int) s.size() && s[i - pal[i]] == s[i + pal[i]]) {
			pal[i]++;
		}

		if(i + pal[i] - 1 > dr) {
			dr = i + pal[i] - 1;
			st = i - pal[i] + 1;
		}
	}

	// cout << s << '\n';
	// for(int i = 0; i < (int) s.size(); i++) {
	// 	cout << pal[i];
	// }
	// cout << '\n';

	long long ans = 0;
	for(int i = 0; i < (int) s.size(); i++) {
		ans += pal[i] / 2;
	}

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