Cod sursa(job #2582060)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 16 martie 2020 12:45:27
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> manacher(string s, bool par)
{
	vector <int> best(s.size(), 0);
	int n = s.size();
	int l = 0;
	int r = 0;
	
	for(int i = 0; i < n - !par; ++i)
	{
		if(i + !par < r)
			best[i] = min(r - i, best[l + r - i - !par]);
		
		int posl = i - best[i] + !par;
		int posr = i + best[i];
		
		while(posl - 1 >= 0 && posr + 1 < n && s[posl - 1] == s[posr + 1])
		{
			--posl;
			++posr;
			++best[i];
		}
		
		if(posr > r)
		{
			r = posr;
			l = posl;
		}
	}
	
	return best;
}

main()
{
	string s;
	fin >> s;
	
	vector <int> par = manacher(s, 0);
	vector <int> impar = manacher(s, 1);
	
	long long cnt = 0;
	
	for(auto i : par)
		cnt += i;
	
	for(auto i : impar)
		cnt += i + 1;
	
	fout << cnt << '\n';
}