Cod sursa(job #3224908)

Utilizator vladdobro07vladdd vladdobro07 Data 16 aprilie 2024 15:14:39
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e6;

vector<int> manacher(2 * nmax + 1);
vector<char> s;

int L = -1, R = -1, mid, mp, st = -1, dr = -1, start, rez = 0;
char ch;

int main() {
	s.push_back('_');
	while(fin >> ch) {
		s.push_back(ch);
		s.push_back('_');
	}
	for(int i = 0; i < s.size(); i++) {
		if(i > R) {
			st = dr = i;

			while(st > 0 && dr < s.size() - 1 && s[st - 1] == s[dr + 1]) {
				manacher[i]++;
				st--;
				dr++;
			}

			L = st;
			R = dr;
		} else {
			mid = (L + R) / 2;
			mp = 2 * mid - i;
			start = R - i;

			if(manacher[mp] < start)
				manacher[i] = manacher[mp];
			else {
				manacher[i] = R - i;

				dr = R;
				st = 2 * i - R;

				while(st > 0 && dr < s.size() - 1 && s[st - 1] == s[dr + 1]) {
					manacher[i]++;
					st--;
					dr++;
				}

				L = st;
				R = dr;
			}
		}
	}
	for(int i = 0; i < s.size(); i ++)
		rez += manacher[i] / 2;
	rez += s.size() / 2;

	fout << rez;
	return 0;
}