Bovine Genomics

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	freopen("cownomics.in", "r", stdin);
	freopen("cownomics.out", "w", stdout);
 
	int N, M;
	cin >> N >> M;
 
	vector<string> g(2 * N);
	for (auto &s : g) cin >> s;
 
	int ans = INT_MAX;
 
	for (int i = 0; i < M; i++) {
		vector<int> v(2 * N);
 
		iota(v.begin(), v.end(), 0);
 
		auto common = [&](int x, int y) {
			int ind = i;
			while (ind < M && g[x][ind] == g[y][ind]) ind++;
			return ind;
		};
 
		auto cmp = [&](int x, int y) {
			int ind = common(x, y);
			return ind < M && g[x][ind] < g[y][ind];
		};
 
		sort(v.begin(), v.end(), cmp);
 
		int mx = i;
 
		for (int j = 0; j < 2 * N - 1; j++) {
			if (v[j] / N != v[j + 1] / N) { mx = max(mx, common(v[j], v[j + 1])); }
		}
 
		if (mx == M) break;
 
		ans = min(ans, mx + 1 - i);
	}
 
	cout << ans << "\n";
}

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	freopen("cownomics.in", "r", stdin);
	freopen("cownomics.out", "w", stdout);
 
	int N, M;
	cin >> N >> M;
 
	vector<string> g(2 * N);
	for (auto &s : g) cin >> s;
 
	vector<int> suf(2 * N);
 
	iota(suf.begin(), suf.end(), 0);
 
	int ans = INT_MAX;
 
	for (int i = M - 1; i >= 0; i--) {
		vector<int> tmp[26];
 
		for (int t : suf) { tmp[g[t][i] - 'A'].push_back(t); }
 
		suf.clear();
 
		for (int j = 0; j < 26; j++) {
			suf.insert(suf.end(), tmp[j].begin(), tmp[j].end());
		}
 
		auto common = [&](int x, int y) {
			int ind = i;
			while (ind < M && g[x][ind] == g[y][ind]) ind++;
			return ind;
		};
 
		int mx = i;
 
		for (int j = 0; j < 2 * N - 1; j++) {
			if (suf[j] / N != suf[j + 1] / N) {
				mx = max(mx, common(suf[j], suf[j + 1]));
			}
		}
 
		if (mx < M) { ans = min(ans, mx + 1 - i); }
	}
 
	cout << ans << "\n";
}