題意：給一個串 $S$，$q$ 次詢問，每次給定串 $T$ 和 $l,r$ ，求有多少個本質不同的串是 $T$ 的子串而不是 $S_{l\dots r}$ 的子串。

$|S|\le 5\times 10^5,q\le 10^5,\sum |T|\le 10^6$

先考慮所有詢問 $l=1,r=|S|$ 怎么做。

先對 $S$ 建個 SAM 出來，我們需要把每次詢問的 $T$ 放上去搞搞。如果用廣義后綴自動機的話復雜度是和 $S$ 有關的，做不了。所以要把 $T$ 就看成一個串。

考慮把 $T$ 放上去匹配，從 SAM 上的當前點不斷跳 fail 直到有對應的轉移邊。這樣可以得到 $T$ 的每一個前綴 $[1,i]$ 最長的 在 $S$ 中出現過的 后綴長度，記為 $le{n}_i$。

但我們要求的是本質不同的串，還需要把上面那個東西去重。

我們一次加入 $T$ 的每個字符，那么當前的一個后綴合法當且僅當其長度大于 $le{n}_i$。我們可以對 $T$ 再單獨建一個 SAM，維護每個結點 endpos 集合中的最大值，然后遍歷每個結點統計答案即可。

然后對于 $l,r$ 任意的情況，就是用可持久化線段樹合并來顯式維護 endpos 集合。

然后就是一通亂搞。

冷靜分析一下，我們要做的是當前維護的串是否在 $S_{l\dots r}$ 中出現過，也就是 $[l+s?1,r]$ 中有沒有這個點的 endpos 集合中的位置，其中 $s$ 為當前串長度。直接暴力丟掉第一個字符，如果當前結點丟完了再跳父親。轉移的時候額外判一下要去的結點對應區間有沒有這個點的 endpos。

因為這個串可能被砍了一半，所以在更新 $le{n}_i$ 的時候要在 $[l,r]$ 里查一個 endpos 的最大值 $mx$，和 $mx?l+1$ 取 $\min$。

復雜度 $\mathrm{O}(n\log n)$

#include <iostream> #include <cstring> #include <cctype> #include <cstdio> #define MAXN 2000005 using namespace std; typedef long long ll; int ch[MAXN<<4][2],sum[MAXN<<4],mxpos[MAXN<<4],cnt; void modify(int& x,int l,int r,int k) {if (!x) x=++cnt;++sum[x];if (l==r) return (void)(mxpos[x]=l);int mid=(l+r)>>1;if (k<=mid) modify(ch[x][0],l,mid,k);else modify(ch[x][1],mid+1,r,k);mxpos[x]=max(mxpos[ch[x][0]],mxpos[ch[x][1]]); } int merge(int x,int y) {if (!x||!y) return x|y;int p=++cnt;ch[p][0]=ch[x][0],ch[p][1]=ch[x][1];ch[p][0]=merge(ch[p][0],ch[y][0]);ch[p][1]=merge(ch[p][1],ch[y][1]);sum[p]=sum[ch[p][0]]+sum[ch[p][1]];mxpos[p]=max(mxpos[ch[p][0]],mxpos[ch[p][1]]);return p; } int query(int x,int l,int r,int ql,int qr) {if (!x) return 0;if (ql<=l&&r<=qr) return sum[x];if (qr<l||r<ql) return 0;int mid=(l+r)>>1;return query(ch[x][0],l,mid,ql,qr)+query(ch[x][1],mid+1,r,ql,qr); } int querymax(int x,int l,int r,int ql,int qr) {if (!x) return 0;if (ql<=l&&r<=qr) return mxpos[x];if (qr<l||r<ql) return 0;int mid=(l+r)>>1;return max(querymax(ch[x][0],l,mid,ql,qr),querymax(ch[x][1],mid+1,r,ql,qr)); } int a[MAXN],c[MAXN],pos[MAXN],n,m; char s[MAXN],t[MAXN]; struct SAM {int ch[MAXN][26],fa[MAXN],len[MAXN],rt[MAXN],mx[MAXN],las,tot;inline void insert(int c,int k,int type){int cur=++tot;int p=las;len[cur]=len[p]+1;for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;if (!p) fa[cur]=1;else{int q=ch[p][c];if (len[q]==len[p]+1) fa[cur]=q;else{int _q=++tot;len[_q]=len[p]+1;fa[_q]=fa[q],fa[q]=fa[cur]=_q;memcpy(ch[_q],ch[q],sizeof(ch[_q]));for (;ch[p][c]==q;p=fa[p]) ch[p][c]=_q;}}las=cur;if (type) modify(rt[cur],1,n,k);else mx[cur]=k;}inline void build(int type){for (int i=1;i<=tot;i++) c[i]=0;for (int i=1;i<=tot;i++) ++c[len[i]];for (int i=1;i<=tot;i++) c[i]+=c[i-1];for (int i=1;i<=tot;i++) a[c[len[i]]--]=i;for (int i=tot;i>=1;i--) if (fa[a[i]]) {if (type) rt[fa[a[i]]]=merge(rt[fa[a[i]]],rt[a[i]]);else mx[fa[a[i]]]=max(mx[fa[a[i]]],mx[a[i]]); }}inline void query(int l,int r){int cur=1,s=0,p=0;for (int i=1;i<=m;i++){while (cur>1&&(!ch[cur][t[i]-'a']||l+s-1>r||!::query(rt[ch[cur][t[i]-'a']],1,n,l+max(s,1)-1,r)))((--s)==len[fa[cur]])&&(cur=fa[cur]);(::query(rt[ch[cur][t[i]-'a']],1,n,l+max(s,1)-1,r))&&(cur=ch[cur][t[i]-'a'],++s,++p);pos[i]=max(0,min(s,querymax(rt[cur],1,n,l,r)-l+1));}}inline ll calc(){ll ans=0;for (int i=1;i<=tot;i++) ans+=max(0,len[i]-max(len[fa[i]],pos[mx[i]]));return ans;}inline void clear(){for (int i=1;i<=tot;i++) mx[i]=fa[i]=0,memset(ch[i],0,sizeof(ch[i]));las=tot=1;}inline SAM():las(1),tot(1){} }S,T; int main() {scanf("%s",s+1);n=strlen(s+1);for (int i=1;i<=n;i++) S.insert(s[i]-'a',i,1);S.build(1);int q;scanf("%d",&q);while (q--){scanf("%s",t+1);m=strlen(t+1);for (int i=1;i<=m;i++) T.insert(t[i]-'a',i,0);T.build(0);int l,r;scanf("%d%d",&l,&r);S.query(l,r);printf("%lld\n",T.calc());T.clear();}return 0; }

總結

以上是生活随笔為你收集整理的【NOI2018】你的名字【后缀自动机】【可持久化线段树合并】【乱搞】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。