Cod sursa(job #2457976)

Utilizator Iulia25Hosu Iulia Iulia25 Data 19 septembrie 2019 11:03:39
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n, ans;
int v[1000005];
char a[1000005];
string s;

int main()  {
	fin >> s;
	a[++n] = '@';
	for (int i = 0; i < s.size(); ++i)  {
		a[++n] = s[i];
		a[++n] = '*';
	}
	a[++n] = '#';
	int l = 1, r = 1, mij = 1;
	for (int i = 2; i < n; ++i)  {
		if (i < r)  {
			if (v[mij - (i - mij)] + i < r)
				v[i] = v[mij - (i - mij)];
			else  {
				int x = v[mij - i + mij] + 1;
				while (a[i + x] == a[i - x])
					++x;
				--x;
				if (i + x > r)
					r = i + x, mij = i;
				v[i] = x;
			}
		} else  {
			int x = 1;
			while (a[i + x] == a[i - x])
				++x;
			--x;
			r = i + x, mij = i;
			v[i] = x;
		}
		if (a[i] == '*')
			ans += (v[i] + 1) / 2;
		else
			ans += v[i] / 2 + 1;
	}
	fout << ans;
	return 0;
}