http://codeforces.com/contest/860/problem/B
N個の9桁の数がある。
各数について、連続部分文字列のうち、他の数の部分文字列に含まれないもので最小のものを答えよ。
前提知識
解説
http://codeforces.com/contest/860/submission/30430457
まずローリングハッシュを用意する。
次に、各数の連続部分文字列のハッシュを作りカウントしておく。
ここから、各数について、全ての連続部分文字列をチェックしていく。
各数の処理に入る前にその数のハッシュを引いておく。
するとカウントされているのは、その数以外のハッシュとなるので、各連続部分文字列のハッシュの個数を見れば、他の数の部分文字列に含まれているかが分かる。
あとは、最小の文字列を答えればいい。
int N; string S[70101]; RollingHash rh[70101]; typedef long long ll; unordered_map<ll, int> cnt; //--------------------------------------------------------------------------------------------------- void _main() { rep(i, 0, 101) { int a = getrand(0, 9); int b = getrand(0, 9); swap(primes[a], primes[b]); } p1 = primes[0], p2 = primes[1]; cin >> N; rep(i, 0, N) cin >> S[i]; // ローリングハッシュ作成 rep(i, 0, N) rh[i].init(S[i], '0'); // 全部のハッシュカウント rep(i, 0, N) rep(L, 0, 9) rep(R, L, 9) { auto p = rh[i].hash(L, R); cnt[1LL * p.first.get() * 1000000010 + p.second.get()]++; } rep(i, 0, N) { rep(L, 0, 9) rep(R, L, 9) { auto p = rh[i].hash(L, R); cnt[1LL * p.first.get() * 1000000010 + p.second.get()]--; } string ans = "1111111111111"; rep(L, 0, 9) rep(R, L, 9) { int ok = 0; auto p = rh[i].hash(L, R); if (cnt[1LL * p.first.get() * 1000000010 + p.second.get()] == 0) ok = 1; string s = S[i].substr(L, R - L + 1); if (ok) if (s.length() < ans.length()) ans = s; } printf("%s\n", ans.c_str()); rep(L, 0, 9) rep(R, L, 9) { auto p = rh[i].hash(L, R); cnt[1LL * p.first.get() * 1000000010 + p.second.get()]++; } } }