General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
58603158 Contestant:
JustInCase
1200E - 47 C++17 (GCC 7-32) Accepted 217 ms 29336 KB 2019-08-11 16:40:04 2019-08-11 18:25:10
→ Source
#include <bits/stdc++.h>

const int32_t MAX_LEN = 1e6;

int32_t encode_char(char c) {
	if(c >= 'a' && c <= 'z') {
		return c - 'a' + 1;
	}
	else if(c >= 'A' && c <= 'Z') {
		return c - 'A' + 27;
	}
	else {
		return c - '0' + 53;
	}
}

struct Hash {
	const static int32_t BASES[];
	const static int32_t MODS[];
	
	static std::vector< int32_t > basePowers[];
	
	static void compute_base_powers() {
		for(int32_t h = 0; h < 2; h++) {
			basePowers[h].push_back(1);
			for(int32_t i = 1; i <= MAX_LEN; i++) {
				basePowers[h].push_back(((int64_t) basePowers[h].back() * BASES[h]) % MODS[h]);
			}
		}
	}

	std::vector< int32_t > vals[2];

	Hash() {}
	Hash(const std::string &s) {
		for(int32_t h = 0; h < 2; h++) {
			vals[h].push_back(encode_char(s[0]));
			for(int32_t i = 1; i < s.size(); i++) {
				vals[h].push_back((vals[h].back() + (int64_t) basePowers[h][i] * encode_char(s[i])) % MODS[h]);
			}
		}
	}

	void append_char(int32_t encodedChar) {
		for(int32_t h = 0; h < 2; h++) {
			int32_t curr = (!vals[h].empty() ? vals[h].back() : 0);
			vals[h].push_back((curr + (int64_t) basePowers[h][vals[h].size()] * encodedChar) % MODS[h]);
		}
	}

	std::pair< int32_t, int32_t > get_subhash(int32_t low, int32_t high) {
		int32_t subHash[2];
		for(int32_t h = 0; h < 2; h++) {
			int32_t lh = (low == 0 ? 0 : vals[h][low - 1]);
			int32_t hh = vals[h][high];
			subHash[h] = (hh - lh + MODS[h]) % MODS[h];
		}

		return { subHash[0], subHash[1] };
	}
};

const int32_t Hash::BASES[] = { 143, 137 };
const int32_t Hash::MODS[] = { (int32_t) 1e9 + 7, (int32_t) 1e9 + 9 };
std::vector< int32_t > Hash::basePowers[2];

Hash h;
std::string ansString = "";

void add_word(const std::string &s) {
	Hash aux = Hash(s);

	int32_t ans = 0;
	for(int32_t i = s.size(); i >= 1; i--) {
		if(i > ansString.size()) {
			continue;
		}

		auto suffHash = h.get_subhash(ansString.size() - i, ansString.size() - 1);
		auto prefHash = aux.get_subhash(0, i - 1);
		
		prefHash.first = ((int64_t) prefHash.first * Hash::basePowers[0][ansString.size() - i]) % Hash::MODS[0];
		prefHash.second = ((int64_t) prefHash.second * Hash::basePowers[1][ansString.size() - i]) % Hash::MODS[1];
		
		if(prefHash == suffHash) {
			ans = i;
			break;
		}
	}

	for(int32_t i = ans; i < s.size(); i++) {
		ansString += s[i];
		h.append_char(encode_char(s[i]));
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	Hash::compute_base_powers();

	int32_t n;
	std::cin >> n;

	for(int32_t i = 0; i < n; i++) {
		std::string s;
		std::cin >> s;

		add_word(s);
	}

	std::cout << ansString << '\n';
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details