題目鏈接：點擊查看
題目大意：給出一個長度為 n 的字符串，再給出 q 個詢問，每次詢問需要回答區間 [ l , r ] 內有多少個本質不同的子串
題目分析：和回文自動機那個題目一樣，n * n 預處理出一個答案數組，然后 O( 1 ) 查詢就好了
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;char s[N];int tot,last,ans[N][N];struct Node
{int ch[26];int fa,len;
}st[N<<1];inline int newnode()
{tot++;for(int i=0;i<26;i++)st[tot].ch[i]=0;st[tot].fa=st[tot].len=0;return tot;
}void add(int x)
{int p=last,np=last=newnode();st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=newnode();st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}}
}void init()
{last=1;tot=0;newnode();
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",s);int n=strlen(s);for(int i=0;i<n;i++){init();int sum=0;for(int j=i;j<n;j++){add(s[j]-'a');sum+=st[last].len-st[st[last].fa].len;ans[i][j]=sum;}}int q;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);l--,r--;printf("%d\n",ans[l][r]);}}return 0;
}
?
總結
以上是生活随笔為你收集整理的HDU - 4622 Reincarnation(后缀自动机-查询区间本质不同子串个数)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
