代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
int n,m,q;
int cnt;
int ls[10000005],rs[10000005],sz[10000005];
char s[2000005],t[2000005];
long long ans;
#define mid ((l+r)>>1)
void update(int &rt,int lst,int l,int r,int pos){
      rt=++cnt;
      sz[rt]=sz[lst]+1;
      if(l==r)return ;
     if(pos<=mid){
        rs[rt]=rs[lst];
        update(ls[rt],ls[lst],l,mid,pos);
     }
     else{
        ls[rt]=ls[lst];
        update(rs[rt],rs[lst],mid+1,r,pos);
     }
}
int query(int rt,int l,int r,int L,int R){
    if(!rt)return 0;
    if(L<=l&&r<=R)return sz[rt];
    int res=0;
    if(L<=mid)res+=query(ls[rt],l,mid,L,R);
    if(R>mid) res+=query(rs[rt],mid+1,r,L,R);
    return res;
}
namespace SAM{
  int lst=1,tot=1;
  int son[1000005][26],fa[1000005],len[1000005],ne[1000005],he[1000005],dfsclk,st[1000005],ed[1000005],pos[10000005],rt[1000005];
  bool pre[1000005]; 
  void extend(int c){
        int np=++tot,p=lst;
        len[np]=len[p]+1;
        pre[np]=1;
        while(p&&!son[p][c])son[p][c]=np,p=fa[p];
        if(!p)fa[np]=1;
        else{
          int q=son[p][c];
          if(len[q]==len[p]+1){
            fa[np]=q;
          }
          else{
             int nq=++tot;
             len[nq]=len[p]+1;
             fa[nq]=fa[q];
             memcpy(son[nq],son[q],sizeof(son[nq]));
             fa[q]=fa[np]=nq;
             while(p&&son[p][c]==q)son[p][c]=nq,p=fa[p];
          }
        }
        lst=np;
   }
  void dfs(int x){
      st[x]=++dfsclk;
      pos[dfsclk]=x;
      for(int i=he[x];i;i=ne[i]){
            dfs(i);
      }
      ed[x]=dfsclk;
  }
  void built(){
       F(i,1,n)extend(s[i]-'a');
       F(i,2,tot){
         ne[i]=he[fa[i]];
         he[fa[i]]=i;
       }
       dfs(1);
       F(i,1,dfsclk){
         if(pre[pos[i]])update(rt[i],rt[i-1],1,n,len[pos[i]]);
         else rt[i]=rt[i-1];
       }
  }
  bool valid(int x,int l,int r){
     if(!x)return 0;
     if(query(rt[ed[x]],1,n,l,r)<=query(rt[st[x]-1],1,n,l,r))return 0;
     return 1;
  }
}
namespace sam{
   int lst=1,tot=1;
   int son[2000005][26],fa[2000005],len[2000005],pos[2000005],lim[2000005];
  void extend(int c,int now){
    int np=++tot,p=lst;
   len[np]=len[p]+1;
   pos[np]=now;
   while(p&&!son[p][c])son[p][c]=np,p=fa[p];
   if(!p)fa[np]=1;
   else{
     int q=son[p][c];
     if(len[q]==len[p]+1){
         fa[np]=q;
     }
     else{
       int nq=++tot;
      len[nq]=len[p]+1;
      fa[nq]=fa[q];
      pos[nq]=pos[q];
      memcpy(son[nq],son[q],sizeof(son[nq]));
      fa[q]=fa[np]=nq;
      while(p&&son[p][c]==q)son[p][c]=nq,p=fa[p];
     }
   }
   lst=np;
  }
  void clear(){
   //Set(son,0);
   F(i,1,tot)F(j,0,25)son[i][j]=0;
     tot=lst=1;
  }
  void built(int l,int r){
      int now=0,p=1;
     F(i,1,m){
         extend(t[i]-'a',i);
       while(1){
          if(SAM::valid(SAM::son[p][t[i]-'a'],l+now,r)){
              now++;
              p=SAM::son[p][t[i]-'a'];
              break;
          }
          if(now==0)break;
          now--;
          if(now==SAM::len[SAM::fa[p]])p=SAM::fa[p];
       } 
       lim[i]=now;
     }
     F(i,2,tot){
        ans+=max(0,len[i]-max(len[fa[i]],lim[pos[i]]));
     }
  }
}
int main () {
    file("name");
     scanf("%s",s+1);
     n=strlen(s+1);
     SAM::built();
     scanf("%d",&q);
     while(q--){
        int l,r;
        scanf("%s%d%d",t+1,&l,&r);
        m=strlen(t+1);
        ans=0;
          sam::built(l,r);
        printf("%lld\n",ans);
        sam::clear();
     }
     return 0;
}

评测结果