下面的 (SAM) 都是默认对于字符串 (s) 的。
定义
SAM 是一张有向无环图，其中，节点被称作状态，边被称作状态间的转移。
图有一个源点 (t_0) ，称作初始状态，其它各节点均可从 (t_0) 出发到达。
每个转移都标有一个字母，从每个节点出发的所有转移所标的字母均不同。
存在若干个终止状态。从初始状态出发走到任意一个终止状态，经过的路径上的所有转移所标的字母连起来一定为 (s) 的一个后缀。(s) 的每个后缀均对应一条这样的路径。
SAM 即为满足以上条件的节点数最少的自动机。
一个性质
任意从初始状态 (t_0) 开始的路径，路径上的所有转移所标的字母连起来一定为 (s) 的一个子串。(s) 的每个子串也都对应着一条这样的路径。
endpos
对于字符串 (s) 的任意非空子串 (t) ，记 (endpos(t)) 为 (t) 在字符串 (s) 中的所有结束位置组成的集合。
若两个子串的 (endpos) 集合相等，则它们在同一等价类中。
可以发现，SAM 的每个状态就对应着一个等价类，所以 SAM 的状态总数就等于等价类的个数 (+1) 。
几个结论
1.若字符串 (s) 的两个子串 (x) ， (y) ((|x|<|y|)) 的 (endpos) 相同，则 (x) 在 (s) 中每次都是以 (y) 的后缀的形式存在的。
2.对于两个非空子串 (x) ， (y) ((|x|<|y|)) ，若 (x) 是 (y) 的后缀，则 (endpos(x) subseteq endpos(y)) ，反之， (endpos(x) cap endpos(y) = varnothing) 。
3.对于一个等价类中的任意两个子串，较短者一定为较长者的后缀。同时，该等价类中的子串长度一定恰好覆盖一整个区间 ([x,y]) 。
link
考虑 SAM 中某个不是源点的状态 (v) ，设它对应的等价类中最长的字符串为 (w) 。该等价类中的其它字符串均为 (w) 的后缀。
可以发现， (w) 的最长几个后缀都存在于这个等价类中，且其它后缀存在于其它等价类中。（因为有空后缀，所以一定会存在这样的后缀）
记 (t) 为最长的这样的后缀，就将 (v) 的后缀链接 (link(v)) 连到 (t) 。
下面，假设初始状态 (t_0) 也为一个只包含自己的等价类（即只包含空串），规定 (endpos(t_0)={0,1,2, cdots ,|s|}) 。
又是几个结论
4.所有后缀链接构成一棵以 (t_0) 为根的树。
后缀链接一定连到严格比当前字符串短的串。
5.通过 (endpos) 集合构造的树与通过后缀链接构造的树相同。
根据上面的结论 (2) ，可以发现 (endpos) 集合构成一棵树。
考虑任意一个不是 (t_0) 的状态 (v) ，可以发现 (endpos(v) subsetneq endpos(link(v))) 。
结合这些，通过后缀链接构造的树本质上就是通过 (endpos) 构造的树。
下面，对于一个状态 (v) ，设
(longest(v)) 为该状态下最长的字符串， (maxlen(v)) 为它的长度。
(shortest(v)) 为最短的字符串， (minlen(v)) 为它的长度。
显然，有 (minlen(v)=maxlen(link(v))+1) 。
构造 SAM
首先，对于初始状态 (t_0) ，指定 (maxlen=0) ， (link=0) 。
设当前要插入的字符为 (c) ，插入 (c) 之前的字符串为 (s) 。
首先，创建一个新状态 (cur) ，对应于字符串 (s+c) 。
设 (last) 为 (s) 对应的状态，则 (maxlen(cur)=maxlen(last)+1) 。
接下来，从 (last) 开始通过后缀链接遍历，对于遍历到的每个状态，尝试增加一条标着 (c) 的转移，如果原来就有了，直接结束循环。
如果最后遍历到了 (0) ，则表示字符串 (s) 中没有出现过 (c) ，所以 (link(cur)=1) 。
反之，假设已经存在的标着 (c) 的转移为 ((p,q)) 。
设状态 (p) 对应于字符串 (x) ，因为 (p) 在 (last) 的后缀链接上，所以 (x) 为 (s) 的后缀。
因为存在 (q) 这个状态，所以 (x+c) 一定作为 (s) 的子串出现过。
此时，我们就要把 (cur) 的后缀链接连到一个满足其中最长的字符串为 (x+c) 的状态上。
若 (q) 满足这个条件，则 (maxlen(q)=maxlen(p)+1) 。
所以，满足上面的式子时， (link(cur)=q) 。
考虑最后一种情况，即 (maxlen(q)>maxlen(p)+1) 的情况。
此时，考虑把 (q) 拆开，使其中一个状态的 (maxlen=maxlen(p)+1) 。
新建一个状态 (v) ，
将 (maxlen(v)) 赋为 (maxlen(p)+1) ，
把 (q) 的所有转移赋给 (v) ，把 (link(v)) 赋为 (link(q)) ，把 (link(q)) 赋为 (v) ，把 (link(cur)) 赋为 (v) 。
最后，遍历一遍 (q) 的后缀链接，直到到了 (0) 或到了一个不能直接转移到 (q) 的状态。
把这些状态到 (q) 的转移改为到 (v) 的转移即可。
void add(char c)
{
int cur=++cnt;
s[cur].len=s[lst].len+1;
int p=lst;
while(p&&!s[p].nxt.count(c))
s[p].nxt[c]=cur,p=s[p].link;
if(!p) s[cur].link=1;
else
{
int q=s[p].nxt[c];
if(s[p].len+1==s[q].len) s[cur].link=q;
else
{
int v=++cnt;
s[v]=s[q],s[v].len=s[p].len+1;
while(p&&s[p].nxt[c]==q)
s[p].nxt[c]=v,p=s[p].link;
s[q].link=v,s[cur].link=v;
}
}
lst=cur;
}
应用
1
检查模式串 (t) 在文本串 (s) 中是否出现。
对 (t) 构造后缀自动机，从 (t_0) 开始根据 (s) 的字符转移，
如果能转移完整个 (s) ，则出现过，反之，没有出现。
2
对于一个 SAM 上的状态 (x) ，它贡献的不重复的子串即为 (maxlen(x)-maxlen(link(x))) 。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int cnt,lst,ans,n;
struct SAM
{
int len,link;
map <int,int> nxt;
}s[N*2];
void add(int c)
{
int cur=++cnt;
s[cur].len=s[lst].len+1;
int p=lst;
while(p&&!s[p].nxt.count(c))
s[p].nxt[c]=cur,p=s[p].link;
if(!p) s[cur].link=1;
else
{
int q=s[p].nxt[c];
if(s[p].len+1==s[q].len) s[cur].link=q;
else
{
int v=++cnt;
s[v]=s[q],s[v].len=s[p].len+1;
while(p&&s[p].nxt[c]==q)
s[p].nxt[c]=v,p=s[p].link;
s[q].link=v,s[cur].link=v;
}
}
ans+=s[cur].len-s[s[cur].link].len,lst=cur;
}
signed main()
{
cnt=1,lst=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
add(x),printf("%lld
",ans);
}
return 0;
}
3
给定一个字符串，计算所有不同子串的总长度。
状态 (x) 的贡献为 (frac{maxlen(x)*(maxlen(x)+1)}{2}-frac{maxlen(link(x))*(maxlen(link(x))+1)}{2}) 。
4
复制一遍串，在 SAM 上贪心地跑 (n) 步即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define fi first
#define se second
#define int long long
using namespace std;
const int N=1e6+10;
int cnt,lst,n,a[N];
struct SAM
{
int len,link;
map <int,int> nxt;
}s[N*2];
void add(int c)
{
int cur=++cnt;
s[cur].len=s[lst].len+1;
int p=lst;
while(p&&!s[p].nxt.count(c))
s[p].nxt[c]=cur,p=s[p].link;
if(!p) s[cur].link=1;
else
{
int q=s[p].nxt[c];
if(s[p].len+1==s[q].len) s[cur].link=q;
else
{
int v=++cnt;
s[v]=s[q],s[v].len=s[p].len+1;
while(p&&s[p].nxt[c]==q)
s[p].nxt[c]=v,p=s[p].link;
s[q].link=v,s[cur].link=v;
}
}
lst=cur;
}
signed main()
{
cnt=1,lst=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) add(a[i]);
for(int i=1;i<=n;i++) add(a[i]);
int p=1;
for(int i=1;i<=n;i++)
{
printf("%lld ",(*s[p].nxt.begin()).fi);
p=(*s[p].nxt.begin()).se;
}
return 0;
}
5
因为要求的是最大值，所以，对于每一个状态，一定只有 (longest) 有用。
设 (f_i) 为 (longest(i)) 出现的次数。
考虑一个状态 (v) ，若 (link(v)=x) ，
那么 (longest(x)) 一定是 (longest(v)) 的后缀。
所以 (f_i=1+ sum limits_{link(x)=i} f_x) 。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e6+10;
int cnt,lst,sz[N*2],n,ans;
char a[N];
vector <int> e[N*2];
struct SAM
{
int len,link;
map <char,int> nxt;
}s[N*2];
int MAX(int x,int y)
{
return x>y?x:y;
}
void add(char c)
{
int cur=++cnt;
s[cur].len=s[lst].len+1;
int p=lst;
while(p&&!s[p].nxt.count(c))
s[p].nxt[c]=cur,p=s[p].link;
if(!p) s[cur].link=1;
else
{
int q=s[p].nxt[c];
if(s[p].len+1==s[q].len) s[cur].link=q;
else
{
int v=++cnt;
s[v]=s[q],s[v].len=s[p].len+1;
while(p&&s[p].nxt[c]==q)
s[p].nxt[c]=v,p=s[p].link;
s[q].link=v,s[cur].link=v;
}
}
sz[cur]=1,lst=cur;
}
void dfs(int x)
{
for(int i=0;i<e[x].size();i++)
dfs(e[x][i]),sz[x]+=sz[e[x][i]];
if(sz[x]!=1) ans=MAX(ans,s[x].len*sz[x]);
}
signed main()
{
cnt=1,lst=1;
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=n;i++) add(a[i]);
for(int i=2;i<=cnt;i++) e[s[i].link].push_back(i);
dfs(1),printf("%lld",ans);
return 0;
}
6
先考虑 (t=0) 的情况。
从初始状态开始顺着 SAM 跑，能选小的字母则选小的字母。
此时，每个点的权值均为 1。
考虑 (t=1) 的情况，其实只是改变了点的权值。
对于每个点，新权值就是以它结尾的不同子串的数量，也就是 5 中的 (f) 。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define int long long
using namespace std;
const int N=1e6+10;
int cnt,lst,sz[N*2],n;
int d[N*2],id[N*2],tp,f[N*2];
char a[N];
struct SAM
{
int len,link;
map <char,int> nxt;
}s[N*2];
int MAX(int x,int y)
{
return x>y?x:y;
}
void add(char c)
{
int cur=++cnt;
s[cur].len=s[lst].len+1;
int p=lst;
while(p&&!s[p].nxt.count(c))
s[p].nxt[c]=cur,p=s[p].link;
if(!p) s[cur].link=1;
else
{
int q=s[p].nxt[c];
if(s[p].len+1==s[q].len) s[cur].link=q;
else
{
int v=++cnt;
s[v]=s[q],s[v].len=s[p].len+1;
while(p&&s[p].nxt[c]==q)
s[p].nxt[c]=v,p=s[p].link;
s[q].link=v,s[cur].link=v;
}
}
f[cur]=1,lst=cur;
}
void O()
{
for(int i=1;i<=cnt;i++) d[s[i].len]++;
for(int i=1;i<=cnt;i++) d[i]+=d[i-1];
for(int i=1;i<=cnt;i++) id[d[s[i].len]--]=i;
for(int i=cnt;i>=1;i--)
{
if(tp) f[s[id[i]].link]+=f[id[i]];
else f[id[i]]=1;
}
f[1]=0;
for(int i=cnt;i>=1;i--)
{
sz[id[i]]=f[id[i]];
for(char j='a';j<='z';j++)
if(s[id[i]].nxt.count(j))
sz[id[i]]+=sz[s[id[i]].nxt[j]];
}
}
void query(int k)
{
if(k>sz[1])
{
puts("-1");
return;
}
int p=1;
while(k) for(char i='a';i<='z';i++)
if(s[p].nxt.count(i))
{
if(sz[s[p].nxt[i]]>=k)
{
k-=f[s[p].nxt[i]],putchar(i),p=s[p].nxt[i];
break;
}
else k-=sz[s[p].nxt[i]];
}
}
signed main()
{
cnt=1,lst=1;
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=n;i++) add(a[i]);
int k;
scanf("%lld%lld",&tp,&k);
O(),query(k);
return 0;
}