hdu 4622 Reincarnation(後綴數組|後綴自動機|KMP)
Reincarnation
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 2138 Accepted Submission(s): 732
Problem Description
Now you are back,and have a task to do:
Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.
And you have some query,each time you should calculate f(s[l...r]), s[l...r] means the sub-string of s start from l end at r.
Input
The first line contains integer T(1<=T<=5), denote the number of the test cases.
For each test cases,the first line contains a string s(1 <= length of s <= 2000).
Denote the length of s by n.
The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.
Output
For each test cases,for each query,print the answer in one line.
Sample Input
2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5
Sample Output
3
1
7
5
8
1
3
8
5
1
Hint
I won't do anything against hash because I am nice.Of course this problem has a solution that don't rely on hash.
Source
2013 Multi-University Training Contest 3
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you: 5065 5064 5062 5061 5059
題意：
給你一個長度不超過2000只由小寫字母組成的字符串。然後q個詢問q不超過10000.每個詢問詢問一個區間[l,r]內有多少不同的子串。
思路：
如果是統計整個串有多少個不同的子串這題就是模板題了。就按照論文上的方法搞就行了。關鍵是要求一個區間有多少不同的子串而不是整個串。但是我們不能對每個詢問都跑一次後綴數組吧。這樣q*n*log(n)肯定T了。但這題用後綴數組還是可做的。但是要對後綴數組有比較深的理解。論文裡統計不同子串的做法利用的就是後綴的前綴就是子串。那麼對於每一個後綴我們可以看它能貢獻多少不同的前綴就是答案了。而這題我們隊整個串跑一邊sa。得到整個串的height數組。可不可以類似處理出來呢。我開始的做法是根據l<=sa[i]<=r來確定這是目標串的後綴。然後只對這個范圍內的串類似論文方式處理。但這樣做是錯誤的。因為你得到的是整個串的sa。
可能存在這樣一種情況。
比如
串為abac
而你詢問為[1,3]
這個區間的sa情況為
3 a
1 aba
2 ba
但是整個串的sa為
1 abac
3 ac
2 bac
4 c
這樣3就排到1的後面去了。
所以我們不能這麼做。我們必須理解統計不同子串的精髓。統計不同後綴貢獻的的前綴。要做到不重不漏。
所以當[l,r]范圍內的一個串i加進去對答案的貢獻必須減掉它和之前所有串重復的部分。也就是和它lcp最大的那個。就行了即為ml。答案就為r-sa[i]+1-min(r-sa[i]+1,ml)。
詳細見代碼:
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=2010;
typedef long long ll;
char txt[maxn];
int sa[maxn],T1[maxn],T2[maxn],ct[maxn],he[maxn],rk[maxn],n,m;
void getsa(char *st)
{
int i,k,p,*x=T1,*y=T2;
for(i=0; i=0; i--)
sa[--ct[x[i]]]=i;
for(k=1,p=1; p=k) y[p++]=sa[i]-k;
for(i=0; i=0; i--) sa[--ct[x[y[i]]]]=y[i];
for(swap(x,y),p=1,x[sa[0]]=0,i=1; i=le&&sa[i]<=ri)
{
ans+=ri-sa[i]+1-min(ri-sa[i]+1,ml);
lcp=he[i+1];
tp=min(lcp,ri-sa[i]+1);
ml=max(ml,tp);
}
}
printf("%d\n",ans);
}
}
return 0;
}
/*
1
lelwprbultllgkhhhyjchhngo
1
15 21
*/
第二種方法是後綴自動機。這個方法就比較簡單了(不代表後綴自動機簡單)。後綴自動機花了很長時間才懂。主要原因感覺網上這方面通俗的資料比較少。也可能是自己太弱了吧。後綴自動機是我學的感覺學起來最難的算法沒有之一。打算打完現場賽自己寫個簡單的學習筆記來拯救像我這樣苦逼的少年。這題只需在後綴自動機結點裡多維護個信息記錄到該節點有多少不同子串就行了。每次就可以知道增加了多少子串。建n次後綴自動機預處理出所有答案就好啦。
詳細見代碼：
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=2010<<1;
typedef long long ll;
struct node
{
node *f,*ch[30];
int len,way;
void init()
{
way=0;
memset(ch,0,sizeof ch);
}
}*root,*tail,sam[maxn<<1];
int tot,dp[2010][2010];
char txt[maxn];
void init()
{
tot=0;
root=tail=&sam[tot++];
root->f=NULL;
root->len=0;
root->init();
root->way=1;
}
void Insert(int c)
{
node *p=tail,*np=&sam[tot++];
np->init(),np->len=p->len+1;
while(p&&!p->ch[c])
{
np->way+=p->way;
p->ch[c]=np,p=p->f;
}
tail=np;
if(!p)
np->f=root;
else
{
if(p->ch[c]->len==p->len+1)
np->f=p->ch[c];
else
{
node *q=p->ch[c],*nq=&sam[tot++];
*nq=*q;
nq->len=p->len+1;
nq->way=0;
q->f=np->f=nq;
while(p&&p->ch[c]==q)
{
p->ch[c]->way-=p->way;
nq->way+=p->way;
p->ch[c]=nq,p=p->f;
}
}
}
}
int main()
{
int i,j,t,len,q,le,ri;
scanf("%d",&t);
while(t--)
{
scanf("%s",txt);
len=strlen(txt);
for(i=0;iway;
}
for(j=i+1;j
第三種事kmp的做法。由於還沒寫代碼。先占個坑吧。
