题面
https://www.luogu.org/problem/P4770
题解
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<cstring> #include<vector> #define ri register int #define LL long long #define nlogn 60500000 #define M 1000050 using namespace std; int n,L0,L1,l,r; char s[M],t[M]; int mat[M]; int ff[M<<1],ch[M<<1][26],len[M<<1]; int root[M<<1]; struct SegmentTree { int ch[nlogn][2],tot; int newnode() { return ++tot; } void insert(int &x,int k,int l,int r){ if (!x) x=++tot; if (l==r) return; int mid=(l+r)/2; if (k<=mid) insert(ch[x][0],k,l,mid); else insert(ch[x][1],k,mid+1,r); } bool have(int x,int lb,int rb,int lc,int rc) { if (!x) return false; if (lb>rc || rb<lc) return 0; if (lc<=lb && rb<=rc) return 1; int mid=(lb+rb)/2; return have(ch[x][0],lb,mid,lc,rc)|have(ch[x][1],mid+1,rb,lc,rc); } int merge(int x,int y){ if (!x || !y) return x|y; int ret=++tot; ch[ret][0]=merge(ch[x][0],ch[y][0]); ch[ret][1]=merge(ch[x][1],ch[y][1]); return ret; } int refind(int now,int lb,int rb) { if (lb==rb) return lb; if (!now) return -1; int mid=(lb+rb)/2; if (ch[now][0]) return refind(ch[now][0],lb,mid); else return refind(ch[now][1],mid+1,rb); } int find(int now,int lb,int rb,int l,int r) { if (lb>r || rb<l || !now) return -1; if (l<=lb && rb<=r) return refind(now,lb,rb); int mid=(lb+rb)/2,t=find(ch[now][0],lb,mid,l,r); if (t!=-1) return t; else return find(ch[now][1],mid+1,rb,l,r); } } segt; vector<int> som[M<<1]; struct SuffixAutoMato { int las,tot; void init() { las=tot=1; } void extend(int c) { int p=las,np=++tot; las=tot; len[np]=len[p]+1; segt.insert(root[np],len[np],1,L0); while (p && ch[p][c]==0) ch[p][c]=np,p=ff[p]; if (!p) ff[np]=1; else { int q=ch[p][c]; if (len[p]+1==len[q]) ff[np]=q; else { int nq=++tot; for (ri i=0;i<26;i++) ch[nq][i]=ch[q][i]; ff[nq]=ff[q]; len[nq]=len[p]+1; ff[np]=ff[q]=nq; while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p]; } } } void maketree() { for (ri i=1;i<=tot;i++) som[ff[i]].push_back(i); } void dp(int x) { for (ri i=0;i<som[x].size();i++) { dp(som[x][i]); root[x]=segt.merge(root[x],root[som[x][i]]); } } } sam; struct SuffixTree { int ff[M<<1],ch[M<<1][26],len[M<<1]; int las,tot; int vis[M<<1],poi[M]; vector<int> son[M<<1]; void init() { for (ri i=1;i<=tot;i++) for (ri j=0;j<26;j++) ch[i][j]=0; for (ri i=1;i<=tot;i++) ff[i]=len[i]=vis[i]=0; for (ri i=1;i<=tot;i++) son[i].clear(); las=tot=1; } void dp(int x) { for (ri i=0;i<son[x].size();i++) { dp(son[x][i]); if (vis[son[x][i]]>vis[x]) vis[x]=vis[son[x][i]]; } } LL query() { for (ri i=1;i<=L1;i++) vis[poi[i]]=mat[i]; for (ri i=1;i<=tot;i++) son[ff[i]].push_back(i); dp(1); LL ret=0LL; for (ri i=1;i<=tot;i++) ret+=min(max(len[i]-vis[i],0),len[i]-len[ff[i]]); init(); return ret; } void extend(int c) { int p=las,np=++tot; las=tot; len[np]=len[p]+1; poi[len[np]]=tot; while (p && ch[p][c]==0) ch[p][c]=np,p=ff[p]; if (!p) ff[np]=1; else { int q=ch[p][c]; if (len[p]+1==len[q]) ff[np]=q; else { int nq=++tot; for (ri i=0;i<26;i++) ch[nq][i]=ch[q][i]; ff[nq]=ff[q]; len[nq]=len[p]+1; ff[np]=ff[q]=nq; while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p]; } } } } st; int main(){ scanf("%s",s+1); L0=strlen(s+1); sam.init(); for (ri i=1;i<=L0;i++) sam.extend(s[i]-'a'); sam.maketree(); sam.dp(1); scanf("%d",&n); st.las=st.tot=1; while (n--) { scanf("%s %d %d",t+1,&l,&r); L1=strlen(t+1); for (ri i=1;i<=L1;i++) st.extend(t[i]-'a'); int now=1,cc=0; for (ri i=1;i<=L1;i++) { if (ch[now][t[i]-'a']) now=ch[now][t[i]-'a'],cc++; else { while (now && !ch[now][t[i]-'a']) now=ff[now]; if (!now) now=1,cc=0; else cc=len[now]+1,now=ch[now][t[i]-'a']; } bool skip=0; while (now && !segt.have(root[now],1,L0,l+len[ff[now]],r)) skip=1,now=ff[now],cc=len[now]; if (!now) now=1,mat[i]=cc=0; else { if (!skip) { if (!segt.have(root[now],1,L0,l+len[now]-1,r)) { int Lb=segt.find(root[now],1,L0,l+len[ff[now]],r); mat[i]=Lb-l+1; if (Lb-l+1>=cc) mat[i]=cc; else mat[i]=cc=Lb-l+1; } else mat[i]=cc; } else if (segt.have(root[now],1,L0,l+len[now]-1,r)) mat[i]=cc=len[now]; else { int Lb=segt.find(root[now],1,L0,l+len[ff[now]],r); mat[i]=cc=Lb-l+1; } } } printf("%lld ",st.query()); } }