C. Concatenating Teams(2).cpp

/*
	To a string not beculiar a few things must happen:
	Looking to a string Ai from A:
		- let P be some prefix of A
		- and S be the rest of string
		- so Ai = P + S
		- then P must be a string in A
		- S must be a prefix of some string in B
		in a way that if there is a Bj in B such 
		that Bj = S + S', and S' also belongs to B
			- because than we will have two concatenated strings 
			generated by different strings, these are:
				Ai + S' = P + Bj
			- so Ai, P, S', and Bj are non peculiar
*/
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

const int MAXN(1'000'000);

const ull P = 31;
ull p[MAXN + 1];
void precompute() {
	p[0] = 1;
	for (int i = 1; i <= MAXN; i++)
	 p[i] = (P * p[i - 1]);
}

struct Hash {
	int n;
	vector<ull> h;
	// vector<ull> hi;
	Hash() {}

	Hash(const string& s) : n(s.size()), h(n) /*, hi(n) */ {
		h[0] = s[0];
		for (int i = 1; i < n; i++)
			h[i] = (s[i] + h[i - 1] * P);
		

		// hi[n - 1] = s[n - 1];
		// for (int i = n - 2; i >= 0; i--)
		// 	hi[i] = (s[i] + hi[i + 1] * P);
	}

	ull query(int l, int r) {
		ull hash = (h[r] - (l ? h[l - 1] * p[r - l + 1] : 0));
		return hash;
	}

	// ull query_inv(int l, int r) {
	// 	ull hash = (hi[l] - (r + 1 < n ? hi[r + 1] * p[r - l + 1] : 0));
	// 	return hash;
	// }
};

pair<int,int> solve(vector<string>& as, vector<string>& bs) {
	// string it self, it's complement, and if belong to bs
	using t = tuple<ull, ull, bool>;
	map<ull, vector<t>> by_S;

	vector<Hash> hash_as;
	set<ull> hashes_as;
	for (auto &ai : as) {
		Hash hash_ai = Hash(ai);
		hash_as.push_back(hash_ai);
		hashes_as.emplace(hash_ai.query(0, hash_ai.n-1));
	}
	
	for (auto &hash_ai : hash_as) {
		int n = hash_ai.n;
		auto full = hash_ai.query(0,n-1);
		for (int i = 0; i < n - 1; i++) {
			auto pref = hash_ai.query(0, i);
			auto suff = hash_ai.query(i+1, n-1);
			if (hashes_as.count(pref)) {
				by_S[suff].push_back({full,pref, 0});
			}
		}
	}

	// save every hash from Bs
	set<ull> bs_full_hashes;
	vector<Hash> bs_hashes;
	for (auto &bi : bs) {
		Hash bi_hash = Hash(bi);
		bs_hashes.emplace_back(bi_hash);
		bs_full_hashes.emplace(bi_hash.query(0, (int)bi.size()-1));
	}

	// See which S are valid
	set<ull> allowed_S;
	for (auto &bi_hash : bs_hashes) {
		int n = bi_hash.n;
		for (int i = 0; i < n -1; i++) {
			auto pref = bi_hash.query(0, i);
			auto suff = bi_hash.query(i+1, n-1);
			if (bs_full_hashes.count(suff)) {
				if (by_S[pref].size() >= 1) {
					allowed_S.emplace(pref);
					by_S[pref].push_back({bi_hash.query(0, n-1), suff, 1});
				}
			}

		}
	}

	// just mark every one as unpeculiar
	set<ull> bad_a, bad_b;
	for (auto &[key, triplets] : by_S) {
		if (allowed_S.count(key) == 0) continue;

		for (auto &[a, b, c ] : triplets) {
			if (c == 0) {
				bad_a.emplace(a);
				bad_a.emplace(b);
			}
			else {
				bad_b.emplace(a);
				bad_b.emplace(b);
			}
		}
	}
	return {as.size() - bad_a.size(), bs.size() - bad_b.size()};
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	precompute();

	int m, n;
	cin >> m >> n;
	vector<string> as(m), bs(n);
	for (auto& ai : as) cin >> ai;
	for (auto& bi : bs) cin >> bi;

	auto [ansa, ansb] = solve(as, bs);

	cout << ansa << ' ' << ansb << '\n';
}

// AC, hashing