代码

#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());
    }
  }
}
namespace solver_std {
  namespace seg_tree {
    const int SIZE = 1e7;
    struct Node {
      int ls, rs;
      int cnt;
    }tree[SIZE];
    int root[MAXN], cnt;
    void build(int &node, int l, int r) {
      node = ++cnt;
      if (l == r) return;
      int mid = (l + r) >> 1;
      build(tree[node].ls, l, mid);
      build(tree[node].rs, mid + 1, r);
    }
    void init() { build(root[0], 1, n); }
    int p;
    int ql, qr, ans;
    void _modify(int &node, int pre, int l, int r) {
      node = ++cnt;
      tree[node] = tree[pre];
      tree[node].cnt++;
      if (l == r) return;
      int mid = (l + r) >> 1;
      if (p <= mid) _modify(tree[node].ls, tree[pre].ls, l, mid);
      else _modify(tree[node].rs, tree[pre].rs, mid + 1, r);
    }
    void modify(int ver, int pos) {
      p = pos;
      _modify(root[ver], root[ver - 1], 1, n);
    }
    void _query(int lnode, int rnode, int l, int r) {
      if (ql <= l && r <= qr) {
        ans += tree[rnode].cnt - tree[lnode].cnt;
        return;
      }
      int mid = (l + r) >> 1;
      if (ql <= mid) _query(tree[lnode].ls, tree[rnode].ls, l, mid);
      if (qr > mid) _query(tree[lnode].rs, tree[rnode].rs, mid + 1, r);
    }
    int query(int a, int b, int l, int r) {
      if (l > r) return 0;
      ql = l, qr = r; ans = 0;
      _query(root[b], root[a - 1], 1, n);
      return ans;
    }
  }
  namespace sam2 {
    const int SIZE = MAXN << 1;
    struct Node {
      int tranc[26];
      int fa, dep;
      int val;
    }tree[SIZE];
    int root, cnt, tail;
    void init() {
      root = cnt = tail = 1;
      memset(tree + 1, 0, sizeof (tree[1]));
    }
    void insert(int x, int v) {
      //fprintf(stderr, "%d %d\n", x, v);
      
      int p = tail, np = ++cnt;
      memset(tree + np, 0, sizeof (tree[np]));
      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[nq].val = 0;
          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;
      tree[np].val = v;
    }
    long long query() {
      static int tot[SIZE];
      for (int i = 0; i <= m; i++) tot[i] = 0;
      for (int i = 1; i <= cnt; i++) {
        tot[tree[i].dep]++;
      }
      static int seq[SIZE];
      for (int i = 1; i <= m; i++) tot[i] += tot[i - 1];
      
      for (int i = 1; i <= cnt; i++) {
        seq[tot[tree[i].dep]--] = i; 
      }

      for (int i = cnt; i >= 1; i--) {
        int x = seq[i];
        tree[tree[x].fa].val = std::max(tree[tree[x].fa].val, tree[x].val);
      }

      long long ans = 0;
      for (int i = 2; i <= cnt; i++) {
        if (tree[i].dep <= tree[i].val) continue;
        ans += tree[i].dep - std::max(tree[tree[i].fa].dep, tree[i].val);
      }

      return ans;
    }

  }
  namespace sam {
    const int SIZE = MAXN << 1;
    struct Node {
      int tranc[26];
      std::vector <int> son;
      int fa, dep;
      int pos;
    }tree[SIZE];
    int root, cnt, tail;
    void insert(int x, int v) {
      
      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[nq].pos = 0;
          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;
      tree[np].pos = v;
    }
    int clk;
    int st[MAXN], en[MAXN];
    void dfs(int u) {
      //fprintf(stderr, "%d\n", u);
      st[u] = clk + 1;
      if (tree[u].pos) {
        ++clk;
        seg_tree::modify(clk, tree[u].pos);
      }
      for (int i = 0; i < (int) tree[u].son.size(); i++) {
        dfs(tree[u].son[i]);
      }
      en[u] = clk;
    }
    void init() {
      root = cnt = tail = 1;
      
      for (int i = 1; i <= n; i++) {
        insert(s[i] - 'a', i);
      }
      for (int i = 2; i <= cnt; i++) {
        tree[tree[i].fa].son.push_back(i);
      }

      seg_tree::init();
      
      dfs(1);
    }
    long long work(int l, int r) {
      int cur = 1;
      static int bnd[MAXN];
      sam2::init();
      int dep = 0;
      for (int i = 1; i <= m; i++) {
        int x = t[i] - 'a';
        for (; cur && !tree[cur].tranc[x]; cur = tree[cur].fa, dep = tree[cur].dep);
        if (!cur) {
          cur = 1; bnd[i] = 0; dep = 0;
        } else {
          dep++;
          cur = tree[cur].tranc[x];
          while(1) {
            bool flag = 0;
            for (int val = std::min(tree[cur].dep, dep); val > tree[tree[cur].fa].dep; val--) {
              if (seg_tree::query(st[cur], en[cur], l + val - 1, r)) {
                bnd[i] = val;
                flag = 1;
                break;
              }
            }
            if (flag) break;
            cur = tree[cur].fa;
            dep = tree[cur].dep;
            if (!cur) {
              cur = 1;
              bnd[i] = 0;
              break;
            }
          }
        }
        //fprintf(stderr, "%d %d %d  ", bnd[i], cur, dep);
        sam2::insert(x, bnd[i]);
      }

      return sam2::query();
    }
  }
  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::work(l, r));
    }
  }
}

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

评测结果