P2336 [SCOI2012] 喵星球上的点名 sol 目前最优解

· · 题解

最优解，乐。

题解区全是很厉害的做法啊，可惜我只能领略一二。

有一种很亲民的做法：哈希，代码巨短无比（当然我的 record 带一个很长的头罢了）。

我们发现一个事实：\sum_{i=1}^x i = O(x^2)，所以说这 n 个串的长度种类数是 O(\sqrt {\sum len}) 的。

我们现在考虑第二问应该怎么做？

我们先处理出这 O(\sqrt {\sum len}) 种长度，然后对于这 n 个双模式串，每个串对这每种长度扫一边。同时记录一个 \text{cnt} 数组，\text{cnt}_x 表示哈希值为 x 的字符串是否已经被记录过，这步的原因是根据题意每个模式串被每个文本串最多点到一次。然后最后输出 \text{cnt} 中有值的位置的个数即可，可以用哈希表来实现。

然后再考虑到第一问：

我们现在已经记录了 \text{cnt} 数组了，可以再记录一个数组 \text{cnt2}，然后每次做完之后让 \text{cnt2} 的每一位加上 \text{cnt}，这样我们就可以统计出 n 个双模式串中每个哈希值出现的次数，然后再遍历那 m 个字符串求哈希之后在 \text{cnt2} 中统计一下即可。

注意你的哈希不要让 \text{hash}(03)=\text{hash}(3)。

时间复杂度 O(m + \sum{len} + n\sqrt {\sum len})。

可以参考一下我的答辩代码：

ull h[N], g[N];
inline ull hsh(int l, int r) {
    if (!l) return h[r];
    return h[r] - h[l - 1] * g[r - l + 1];
}
hash_map vis, mp;
unordered_map<ull, int> mp_;
int n, m, ans[N];
int main() {
    read(n), read(m), g[0] = 1;
    for (int i = 1; i < N; i++) g[i] = g[i - 1] * P;
    for (int i = 1; i <= n; i++) {
        int x, y;
        read(x); while (x--) read(y), ++y, str[i].push_back(y);
        read(x); while (x--) read(y), ++y, str2[i].push_back(y);
    }
    vector<int> v;
    for (int i = 1; i <= m; i++) {
        int x, y;
        read(x), v.emplace_back(x); ull ans = 0;
        while (x--) read(y), ++y, ans = ans * P + y; 
        f[i] = ans, ++vis[ans];
    }
    sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++) {
        clear(mp_), h[0] = str[i][0];
        int res = 0;
        for (int j = 1; j < str[i].size(); j++) h[j] = h[j - 1] * P + str[i][j];
        for (int len : v)
            for (int j = len - 1; j < str[i].size(); j++) {
                ull tmp = hsh(j - len + 1, j);
                if (vis.count(tmp) && !mp_.count(tmp)) ++mp_[tmp], res += vis[tmp];
            }
        h[0] = str2[i][0];
        for (int j = 1; j < str2[i].size(); j++)
            h[j] = h[j - 1] * P + str2[i][j];
        for (int len : v)
            for (int j = len - 1; j < str2[i].size(); j++) {
                ull tmp = hsh(j - len + 1, j);
                if (vis.count(tmp) && !mp_.count(tmp)) ++mp_[tmp], res += vis[tmp];
            }
        ans[i] = res;
        for (auto [u, v] : mp_) ++mp[u];
    }
    for (int i = 1; i <= m; i++) write(mp[f[i]]), putc('\n');
    for (int i = 1; i <= n; i++) write(ans[i]), putc(' ');
    do_flush();
    return 0;
}