【悬关】为何字符串哈希会被卡？

过了中间四个点。

思路：

对于每个前缀，用哈希存一遍。可以发现总共最多只会存 3\times10^6 遍。且每次插入必定是 O(1) 的。（因为我是在插入的同时计算当前的哈希值，所以复杂度就算进插入里了）

储存我是用双哈希，因为直接比较字符串的复杂度开销很大。查询的期望时间复杂度是 O(\frac{n}{m} \log \frac{n}{m})（使用了 set 去重），其中我设 m=10^6+7。

清空我只清空用过的，顶多就只会清空 \sum\lvert S_i\rvert 个 list 中的顶多 \sum\lvert S_i\rvert 个元素，应该不会有什么问题吧。

总的时间复杂度应该是 O(\sum\lvert S_i\rvert +\frac{n}{m} \log \frac{n}{m})。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD(1e6+7);
const int BASE1(131);
const int BASE2(13331);

int t, n, q, ha1, base1;
unsigned int ha2, base2;
string str, tmp;
list<pair<unsigned int, int>> li[MOD];
vector<int> vec;

void clear(){
    for (int i: vec) li[i].clear();
    vec.clear();
}

void insert(string str, int ha1, int ha2, int ind){
    vec.push_back(ha1);
    li[ha1].push_back({ha2, ind});
}

int query(string str){
    set<int> st;

    ha1 = ha2 = 0;
    base1 = base2 = 1;
    for (char i: str){
        ha1 = (ha1 + i * base1) % MOD;
        base1 = (base1 * BASE1) % MOD;
        ha2 += i * base2;
        base2 *= BASE2;
    }

    for (auto i: li[ha1]){
        if (i.first == ha2) st.insert(i.second);
    }
    return st.size();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--){
        cin >> n >> q;
        clear();
        for (int i(1); i<=n; ++i){
            cin >> str;
            tmp = "";

            ha1 = ha2 = 0;
            base1 = base2 = 1;
            for (char j: str){
                ha1 = (ha1 + j * base1) % MOD;
                base1 = (base1 * BASE1) % MOD;
                ha2 += j * base2;
                base2 *= BASE2;

                tmp += j;
                insert(tmp, ha1, ha2, i);
            }
        }
        while (q--){
            cin >> str;
            cout << query(str) << '\n';
        }
    }

    return 0;
}