代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
const int MAXN = 1e6 + 10;

char s[MAXN], t[MAXN];
int n, m, q;
namespace solver1 {
  namespace sam {
    const int SIZE = 2e6;
    struct Node {
      int tranc[26];
      int fa, dep;
      int ver, cnt, to;
    }tree[SIZE];
    int root, cnt, tail, tot;
    int tot_time;
    std::vector <int> pts;
    Node backup[MAXN];
    void insert(int x) {
      int p = tail, np = ++cnt;
      tree[np].dep = tree[p].dep + 1;
      for (; p && !tree[p].tranc[x]; p = tree[p].fa) tree[p].tranc[x] = np;
      if (!p) {
        tree[np].fa = root;
      } else {
        int q = tree[p].tranc[x];
        if (tree[q].dep == tree[p].dep + 1) {
          tree[np].fa = q;
        } else {
          int nq = ++cnt;
          tree[nq] = tree[q];
          tree[nq].dep = tree[p].dep + 1;
          tree[q].fa = tree[np].fa = nq;
          for (; p && tree[p].tranc[x] == q; p = tree[p].fa) tree[p].tranc[x] = nq;
        }
      }
      tail = np;

    }
    void init() {
      tail = root = cnt = 1;
      
      for (int i = 1; i <= n; i++) {
        insert(s[i] - 'a');
      }

      for (int i = 1; i <= cnt; i++) {
        tree[i].cnt = 1;
        tree[i].to = i;
      }
      tot = cnt;
      std::copy(tree + 1, tree + cnt + 1, backup + 1);
    }
    void copy_node(int &x) {
      return;
      if (tree[x].ver != tot_time) {
        int u = ++cnt;
        tree[u] = tree[x];
        tree[u].ver = tot_time;
        tree[u].to = u;
        
        tree[x].ver = tot_time;
        tree[x].to = u;
        
        
        if (x == root) {
          root = u;
        }
        x = u;
      } else {
        x = tree[x].to;
      }
    }
    
    int newnode() {
      int u = ++cnt;
      memset(tree + u, 0, sizeof tree[u]);
      tree[u].ver = tot_time;
      pts.push_back(u);
      return u;
    }
    void insert2(int x) {
      int p = tail, np;
      if (!tree[p].tranc[x]) {
        np = newnode();
      } else {
        np = tree[p].tranc[x];

        if (tree[np].dep != tree[p].dep + 1) {
          copy_node(np);
          int nq = newnode();
          tree[nq] = tree[np];
          tree[nq].dep = tree[p].dep + 1;
          tree[np].fa = nq;
          for (; p && tree[p].tranc[x] == np; p = tree[p].fa) {
            copy_node(p);
            tree[p].tranc[x] = nq;
          }
         
          tail = nq;
        } else {
          tail = np;
        }
        return;
      }
      
      tree[np].dep = tree[p].dep + 1;
      for (; p && !tree[p].tranc[x]; p = tree[p].fa) {
        copy_node(p);
        tree[p].tranc[x] = np;
      }
      
      if (!p) {
        tree[np].fa = root;
      } else {
        int q = tree[p].tranc[x];
        if (tree[q].dep == tree[p].dep + 1) {
          tree[np].fa = q;
        } else {
          int nq = newnode();
          tree[nq] = tree[q];
          tree[nq].dep = tree[p].dep + 1;
          copy_node(q);
          tree[q].fa = tree[np].fa = nq;
          for (; p && tree[p].tranc[x] == q; p = tree[p].fa) {
            copy_node(p);
            tree[p].tranc[x] = nq;
          }
        }
      }
      tail = np;
    }
    
    long long query() {
      ++tot_time;
      cnt = tot;
      root = 1;
      tail = root;
      std::copy(backup + 1, backup + cnt + 1, tree + 1);

      pts.clear();
      
      for (int i = 1; i <= m; i++) {
        insert2(t[i] - 'a');
      }

      long long ans = 0;
      for (int i = 0; i < (int) pts.size(); i++) {

        int k = pts[i];
        if (!tree[k].cnt) {
          ans += tree[k].dep - tree[tree[k].fa].dep;
        }
      }


      return ans;
    }
    
  }
  void main() {
    sam::init();
    while(q--) {
      int l, r;
      scanf("%s%d%d", t + 1, &l, &r);
      m = strlen(t + 1);
      printf("%lld\n", sam::query());
    }
  }
}

int main() {
  //freopen("name.in", "r", stdin);
 //freopen("name.out", "w", stdout);
  scanf("%s", s + 1);
  n = strlen(s + 1);
  scanf("%d", &q);
  solver1::main();
  
}

评测结果