はまやんはまやんはまやん

hamayanhamayan's blog

Polycarp's phone book [Codeforces Round #434 B]

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()]++;
        }
    }
}