SAM（后缀自动机）模板

SAM（后缀自动机）模板

个人感觉这个SAM比SA要难理解的多，两者好像功能有相似之处，不过SAM在一些题目上有它的优势
把板子和模板题记录下来，方便以后抄标

学习小记

模板题：【GDOI2012】字符串

Description

mmm正在学习字典序。现在老师给她布置了一个作业：给出一个字符串，问该字符串的所有不同的子串中，按字典序排第K的字串。由于众所周知的原因，mmm需要你为她解决这个问题。

Input

第1行输入一个只有小写字母组成的字符串。
第2行输入N，为询问个数。
第3到N+2行每行输入一个整数Ki。

Output

输出N行，第i行输出按字典序排第Ki的子串，如果Ki超出了子串数量，输出-1.

Sample Input

abbb
8
1
2
3
4
5
6
7
8

Sample Output

a
ab
abb
abbb
b
bb
bbb
-1

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 20100
using namespace std;
char s[N];
int n,last=1,tot=1,a[N],b[N*10],q,sum[N*10];
struct SAM{int len,size,fail;int to[26];
}t[N*10];
void add(int x)
{int p=last,np=++tot;t[np].len=t[p].len+1;t[np].size=1;last=np;for(;p&&t[p].to[x]==0;p=t[p].fail) t[p].to[x]=np;if(p==0){t[np].fail=1;return;}int q=t[p].to[x];if(t[p].len+1==t[q].len) t[np].fail=q;else{int nq=++tot;t[nq]=t[q];t[nq].len=t[p].len+1;t[q].fail=t[np].fail=nq;for(;p&&t[p].to[x]==q;p=t[p].fail) t[p].to[x]=nq;}
}
void ssort()
{fo(i,1,tot) a[t[i].len]++;fo(i,1,n) a[i]+=a[i-1];fd(i,tot,1) b[a[t[i].len]--]=i;
}
void bfs(int k)
{int x=1;while(k>t[x].size){k-=t[x].size;fo(i,0,25)if(t[x].to[i]>0){if(sum[t[x].to[i]]>=k){x=t[x].to[i];putchar(i+97);break;}k-=sum[t[x].to[i]];}   }putchar('n');
}
int main()
{scanf("%sn",s+1);n=strlen(s+1);fo(i,1,n) add(s[i]-97);ssort();fd(i,tot,1){int x=b[i];sum[x]=t[x].size;fo(i,0,25) sum[x]+=sum[t[x].to[i]];}scanf("%d",&q);while(q--){int k;scanf("%d",&k);if(k>sum[1]) {printf("-1n");continue;}bfs(k);}
}