借用代码

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
typedef long long ll;
const int N = 1e5 + 5, P = 131;
string s[N], t;
ull g[N];
ull qsm(ull a, int b) {
    ull res = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ull h[N], p[N];
ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
void solve() {
    int n, m;
    cin >> n >> m;
    map<ull, int> mp;
    set<int> st;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ull res = 0;
        for (auto c : s[i]) {
            res = res * P + c;
        }
        st.insert(s[i].size());
        g[i] = res;
        mp[res]++;
    }
    while (m--) {
        int op, x, y;
        cin >> op;
        if (op == 0) {
            cin >> x >> y >> t;
            mp[g[x]]--;
            g[x] -= s[x][y - 1] * qsm(P, s[x].size() - y);
            g[x] += t[0] * qsm(P, s[x].size() - y);
            s[x][y - 1] = t[0];
            mp[g[x]]++;
        } else {
            cin >> t;
            p[0] = 1;
            for (int i = 1; i <= t.size(); i++) {
                h[i] = h[i - 1] * P + t[i - 1];
                p[i] = p[i - 1] * P;
            }
            ll res = 0;
            for (auto len : st) {
                for (int i = 1; i + len - 1 <= t.size(); i++) {
                    ull cs = get(i, i + len - 1);
                    if (mp.count(cs)) res += mp[cs];
                }
            }
            cout << res << endl;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}