Cod sursa(job #2260548)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 15 octombrie 2018 09:39:43
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <vector>
#include <cstring>
#include <fstream>

using namespace std;

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

const long long Dim = 1e6 + 5;
long long n,LC[Dim * 2],l = 0,r = -1,k;
char T[Dim];
vector < char > b;

int main() {
	
	fin >> ( T + 1 ); 
	long long n = strlen( T + 1 );
	for ( long long i = 1; i <= n; ++i) {
		b.push_back('*');
		b.push_back(T[i]);
	} b.push_back('*');
	for ( long long i = 0; i < b.size(); ++i) {
		if ( i > r)
			k = 0;
		else
			k = min(LC[l +r - i],r - i);
		while ( i + k < b.size()and i - k >= 0 and b[i+k] == b[i-k])
			k++;
		LC[i] = k--;
		if ( i + k > r)
		 l = i - k , r = i + k;
	}
	long long ans = strlen(T + 1);
	for ( long long i = 0; i < b.size(); ++i)
		ans += (LC[i] - 1) / 2LL;
	fout << ans;
}