Cod sursa(job #2458013)

Utilizator Iulia25Hosu Iulia Iulia25 Data 19 septembrie 2019 11:59:12
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n;
long long ans;
int v[2000010];
char a[2000010];
string s;

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