字尾自動機
摘要：
字串：新演算法，新自閉
給定字串s的字尾自動機是一個接受所有字串s的字尾的最小DFA（確定性有限自動機或確定性有限狀態自動機）。
性質：
字尾自動機是一張有向無環圖。頂點是狀態，邊是狀態之間的轉移。
初始狀態為...
字串：新演算法，新自閉
- 給定字串s的字尾自動機是一個接受所有字串s的字尾的最小DFA（確定性有限自動機或確定性有限狀態自動機）。
-
性質：
- 字尾自動機是一張有向無環圖。頂點是狀態，邊是狀態之間的轉移。
- 初始狀態為\(t_0\) ,它是這張圖的源點。
- 每個轉移代表一個字母。從一個頂點出發的所有轉移都不同。
- 一個或多個狀態為終止狀態。如果我們從初始狀態出發，最終轉移到了一個終止狀態，所形成的一個串必定是s的一個字尾。
- 字尾自動機是所有滿足以上條件的自動機中頂點數最少的一個。
-
幾個小理解：
- 字尾自動機上每一個節點代表了一個endpos等價類，並且從\(t_0\) 走到當前節點形成的子串一定是這個節點所代表的endpos等價類中長度最長的子串。
- 每一條返祖邊都對應了parent樹上的一條邊。且返祖邊練的一定是不屬於當前endpos等價類的一個最長字尾。
- 在parent樹上，父節點一定是子節點的字尾。
- 構圖是為了實現，從初始狀態走可以訪問到s所有的字尾。
-
t=0，求本質不同的第k小串。
- 想要保證字典序的一個順序，那我們肯定是在後綴自動機上搞事情。因為在初始狀態轉移的時候，可以保證字典序。
- 而後綴自動機上每一個節點維護的是什麼？一個節點代表一個等價類，同時它也代表了從初始狀態到這個點所形成的一個子串。我們可以維護經過每一個點有多少個串。即以這個子串為字首有多少個串。設\(sum[i]\) 表示經過i節點的子串數量，如果我們處理出了sum陣列，那麼直接類似線段樹求第K大，二分查詢就好了。
- 怎麼處理出sum陣列？考慮字尾自動機是一張有向無環圖，我們按照拓撲序跑一遍是可以求出sum陣列的。並且我們知道，一個節點向另一個節點連一條邊，那麼這個節點的長度一定小於另一個點的長度。因此我們仍然用桶按照長度從小到大排序，倒序處理，和拓撲序是等價的。（注意這個處理與求siz陣列的不同）。初始值，sum=siz=1。
- t=1，相同的子串出現在不同位置，算作不同子串。那麼初始值的時候，siz還是siz，不強制賦值為1就好了。
Coding
#include<bits/stdc++.h>
#define rint register int
#define ll long long
using namespace std;
const int N=1e6+10;
int t,n,tot=1,la=1,siz[N],ne[N][30],fa[N],len[N],c[N],A[N];
char s[N];ll sum[N],k;
void add(int c){
rint p=la,np=la=++tot;siz[tot]=1;len[tot]=len[p]+1;
for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=np;
if(!p) fa[np]=1;
else{
rint q=ne[p][c];
if(len[p]+1==len[q]) fa[np]=q;
else{
rint nq=++tot;
memcpy(ne[nq],ne[q],sizeof(ne[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
len[nq]=len[p]+1;
for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=nq;
}
}
}
void dfs(int p,int num){
if(num<=siz[p]) return;
num-=siz[p];
for(int i=0;i<26;++i){
if(sum[ne[p][i]]>=num){
putchar(i+'a');
dfs(ne[p][i],num);
return ;
}else num-=sum[ne[p][i]];
}
}
int main(){
scanf("%s",s+1);
scanf("%d %lld",&t,&k);
n=strlen(s+1);
for(rint i=1;i<=n;++i) add(s[i]-'a');
for(rint i=1;i<=tot;++i) c[len[i]]++;
for(rint i=1;i<=tot;++i) c[i]+=c[i-1];
for(rint i=1;i<=tot;++i) A[c[len[i]]--]=i;
for(rint i=tot;i>0;--i){
rint p=A[i];
siz[fa[p]]+=siz[p];
}
for(rint i=1;i<=tot;++i) t==0?(sum[i]=siz[i]=1):(sum[i]=siz[i]);
siz[1]=sum[1]=0;
for(rint i=tot;i>0;--i){
rint p=A[i];
for(int j=0;j<26;++j) sum[p]+=sum[ne[p][j]];
}
if(sum[1]<k) cout<<-1<<endl;
else dfs(1,k),cout<<endl;
return 0;
}