CROC 2016 - Qualification C. Hostname Aliases

問題

codeforces.com

解法

各ホストについて, 出てくるパスを sort -> erase することによってまとめます。パスについては, 両端に "$" を挟むような形にして各パスが独立になるようにしておきましょう(そうしないと "ab", "cd" っていうのと "abc", "d" っていうパスを区別出来ない)。

で, RollingHash などでパスの情報を圧縮してその情報についてソートします。これで連続した要素に同じハッシュ値があったら同じグループに入れましょう。

struct RollingHash {
    static const ll mul0=10009,mul1=10007;
    static const ll add0=1000010007, add1=1003333331;
    string s; int l;
    vector<ll> hash_,pmo_;
    void init(string s) {
        this->s=s; l=s.size();
        hash_.resize(l+1); pmo_.resize(l+1);
        hash_[0]=0; pmo_[0]=1;
        for (int i = 0; i < l; i++) pmo_[i+1]=pmo_[i]*mul1;
        for (int i = 0; i < l; i++) hash_[i+1]=(hash_[i]*mul1+add1+s[i]);
    }
    ll hash(int l,int r) { // s[l..r]
        return hash_[r+1]-hash_[l]*pmo_[r+1-l];
    }
};

pair<string, string> calc(const string& s) {
    pair<string, string> ret;
    ret.first += s.substr(0, 7);
    int i;
    for (i = 7; i < (int)(s.size()); i++) {
        if (s[i] == '/') break;
        ret.first += s[i];
    }
    ret.second = "$" + s.substr(i) + "$";
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<string, vector<string> > mp;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        auto p = calc(s);
        mp[p.first].push_back(p.second);
    }
    vector<pair<pli, string>> memo(mp.size());
    {
        int i = 0;
        for (auto& p : mp) {
            sort(p.second.begin(), p.second.end());
            p.second.erase(unique(p.second.begin(), p.second.end()), p.second.end());
            string s;
            int flag = 0;
            for (string t : p.second) {
                if (t.empty()) flag = 1;
                s += t;
            }
            RollingHash rh;
            rh.init(s);
            memo[i++] = make_pair(pli(rh.hash(0, s.size()-1), flag), p.first);
        }
    }
    sort(memo.begin(), memo.end());
    int sz = memo.size();
    vector<vector<string> > ans;
    for (int i = 0; i < sz; ) {
        int j = i+1;
        while (j < sz && memo[j].first == memo[i].first) j++;
        if (j-i > 1) {
            vector<string> tmp;
            for (int k = i; k < j; k++) {
                tmp.push_back(memo[k].second);
            }
            ans.push_back(tmp);
        }
        i = j;
    }
    cout << ans.size() << endl;
    for (auto ss : ans) {
        for (string s : ss) cout << s << " ";
        cout << endl;
    }
    return 0;
}