求助ac自动机65pts

#include <iostream>
#include <queue>

using namespace std;

const int kMaxN = 4e6 + 1;

int n, q;
string t[kMaxN];

class ACAM {
 private:
  static const int kMaxS = 27;
  struct N {
    vector<int> t;
    int c = 0, f, ts; // timestamp

    N() { t.resize(kMaxS); }
    void reset() {
      fill(t.begin(), t.end(), 0);
      c = 0, f = 0;
    }
  };

  int tot = 0;
  vector<N> v;

 public:
  ACAM() { v.resize(1); }

  void insert(string s) {
    int p = 0;
    for (char c : s) {
      int o = c - 'a';
      if (c == '#') {
        o = 26;
      }
      if (!v[p].t[o]) {
        v.emplace_back(N());
        v[p].t[o] = v.size() - 1;
      }
      p = v[p].t[o];
    }
    v[p].c++;
  }

  void build() {
    queue<int> q;
    for (int i = 0; i < kMaxS; i++) {
      if (v[0].t[i]) {
        q.push(v[0].t[i]);
      }
    }
    for (int x; q.size(); q.pop()) {
      x = q.front();
      for (int i = 0; i < kMaxS; i++) {
        if (v[x].t[i]) {
          v[v[x].t[i]].f = v[v[x].f].t[i];
          q.push(v[x].t[i]);
        } else {
          v[x].t[i] = v[v[x].f].t[i];
        }
      }
    }
  }

  int query(string s) {
    tot++;
    int ans = 0, p = 0;
    for (int i = 0; i < s.size(); i++) {
      int o = s[i] - 'a';
      if (s[i] == '#') {
        o = 26;
      }
      p = v[p].t[o];
      for (int l = p; l && v[l].ts != tot; l = v[l].f) {
        ans += v[l].c;
        v[l].ts = tot;
      }
    }
    return ans;
  }
} ac;

string merge(string a, string b) {
  string r = "";
  int c0 = 0;
  while (c0 < a.size() && a[c0] == b[c0]) {
    c0++;
  }
  // cout << c0 << '\n';
  int c1 = a.size() - 1;
  while (c1 >= 0 && a[c1] == b[c1]) {
    c1--;
  }
  // cout << c1 << '\n';
  c0--, c1++;
  if (c1 == 0) {
    r = "#" + a + "#";
  } else {
    r = "";
    for (int j = 0; j <= c0; j++) {
      r += a[j];
    }
    r += "#";
    for (int j = c0 + 1; j < c1; j++) {
      r += a[j];
    }
    for (int j = c0 + 1; j < c1; j++) {
      r += b[j];
    }
    r += "#";
    for (int j = c1; j < a.size(); j++) {
      r += a[j];
    }
  }
  return r;
}

int main() {
  ios::sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    string t1, t2;
    cin >> t1 >> t2;
    t[i] = merge(t1, t2);
    // cout << t[i] << '\n';
    ac.insert(t[i]);
  }
  ac.build();
  for (string s1, s2, s; q; q--) {
    cin >> s1 >> s2;;
    if (s1.size() != s2.size()) {
      cout << "0\n";
      continue;
    }
    s = merge(s1, s2);
    cout << ac.query(s) << endl;
  }
  return 0;
}