给一个可以画出 SAM 结构的网站。（从机房大佬那里偷的）
但听管理大大说这个东西画广义 SAM 的时候有点问题，详细见洛谷讨论 悲惨故事 长文警告 关于广义 SAM 的讨论。
然后洛谷管理大大给了一个他自己做的网站：SAM Visualizer。就是好像会在随机时间 404 掉。
模板
简介
SAM 几乎可以算是信息竞赛中字符串的终极解决方案。几乎所有的比较难的字符串题都可以通过 SAM 的性质结构之类的东西延伸出来。
事实上，更准确的说 SAM 更像数据结构，是一种与 tire 树类似的东西。
其结构是一张 DAG 与 一棵树的和，这二者的点集都是一样的。DAG 上的边与 trie 上的类似，都是表示一个字母。
通过走 DAG 上的边，我们可以表示这个字符串的所有子串，通过走 parent 树上的边，我们可以表示所有当前节点表示的子串的所有后缀。
endpos
endpos 实际上是一个集合。具体而言，endpos 是 \(s\) 的字串 \(s'\) 在 \(s\) 中出现位置的末尾的集合。
因此，根据定义，显然有性质：（下面简写 endpos 为edp，\(edp(a)\) 表示字串 \(a\) 的 edp 集合，所有 edp 集合相同的字串所构成的集合成为 edp 等价类）
- \( edp(a)\subseteq edp(b)\Leftrightarrow b\) 是 \(a\) 的后缀
- \( edp(a)\nsubseteq edp(b)\Leftrightarrow b\) 不是 \(a\) 的后缀
- 同一 edp 等价类中所有字符串长度不等且连续
我们发现一个 edp 等价类里的所有字串具有类似的性质，因此我们考虑将所有 edp 等价类的字串变成一个点来看待。
根据简介里的介绍，我们发现如果我们创建出一张 DAG，可以像 trie 一样通过走 DAG 上的边到达所有后缀，那么就可以表示所有子串了。（任意一个子串都一定是某个后缀的前缀）
这个就是其叫“后缀自动机”的理由，我们从根节点走到叶子结点一定表示了一个原串的后缀，而我们将所有某个 edp 等价类中的点压缩到了一个节点上，这样就形成了一个 DAG。
这里以 abbb 为例。请先忽略掉红色的边。
后缀链接 \(link\) 及parent树
由于一个 edp 等价类中所有的字符串长度相同且连续，因此如果我们将某个 edp 等价类中的最短的那个字符串的最前面的字符删去，那么新得到的这个更短的字符串就一定在更多的地方出现过。
我们将更短的这个字符串所在的 edp 等价类所对应的点与原来的 edp 等价类所对应的点连边。这就是所谓的后缀链接。
根据定义，我么可以发现空字符串所对应的节点不会有边连出，而其他每个节点有且仅有一条边连出。因此所有的后缀链接以及点构成了一棵树。我们将这棵树称作 parent 树。对于一个点 \(u\)，我们将其连出的后缀链接所指向的点称作 \(fa_u\)。
反过来看，如果我们将连边的过程看成在当前节点对应的最长的字符串前面加点，然后向加点的字符串的对应的点连边，那么显然可以看出其子节点的 edp 集合是当前点的 edp 集合的一个划分，其所有子集和的 edp 集合不交且包含于当前节点的 edp 集合。
不过需要注意的是，其所有子节点的 edp 集合的并可能并不是其的 edp 集合。
我们设 \(len_u\) 表示节点 \(u\) 所代表的所有字符串中最长的长度，\(minlen_u\) 表示最短的长度。根据定义显然有 \(minlen_u-1=len_{fa_u}\)。这个结论比较重要。
仍然是那个例子，按照上面的定义将后缀链接建出来就是上面那张图中红色的边。点上的 \(Max\) 表示的就是这个点所对应的 \(len\)。
线性构造
然后就来考虑如何建出这两个东西。我们通过一个一个将字符插入进 SAM 来构造。假设我们当前插入的是字符 \(s_i\)，而 \([1,i-1]\) 所代表的字符串的 SAM 已经构建完毕。
在具体讲述之前，先需要强调的是我们不具体保存下来每一个点所对应的 edp 集合是什么以及所对应的字符串是什么。我们只是存下来了后缀链接、DAG 上的边和 \(len\)。（\(minlen\) 不需要记是因为可以通过 \(fa\) \(O(1)\) 求）
我们设 \(lst\) 表示前 \(i-1\) 个字符所对应的字符串所在的节点编号。
显然对于一个新的字符及其位置，我们需要一个新的点来表示，设为 \(u\)。而且其 \(len\) 一定 \(len_{lst}+1\)。
我们假设一个变量 \(p\)，其初始值是 \(lst\)。可以发现如果 \(p\) 所对应的点在 DAG 上没有 \(s_i\) 的出边，那么在这个点所对应的所有字符串后面都加上一个 \(s_i\)，那么这所有新的字串的 edp 一定都包含 \(i\) 这个位置。因此我们将 \(p\) 新增一条在 DAG 上的指向 \(u\) 的边。注意这时 \(p\) 是 \(lst\)，\(lst\) 的 edp 集合中一定有 \(i-1\) 这个位置。
然后发现如果令 \(p\gets fa_p\) 并且跳了 parent 树上的边后新的 \(p\) 在 DAG 上 仍然没有 \(s_i\) 这条边，上述逻辑依然成立。注意，在 parent 树上跳 \(fa\) 本质上是在前面删去节点，跳后节点中的所有子串一定是跳前节点中子串的真后缀。这样 \(p\) 中的所有子串的 edp 集合中仍然一定有 \(i-1\) 这个位置。
如果 \(p\) 一直到达最初表示空串的节点，那么表示这个字符是新出现的，将 \(fa_u\) 设为表示空串的节点即可。
如果某个时刻 \(p\) 在 DAG 上有这条边，那么设 \(q\) 为 \(p\) 走 DAG 上 \(s_i\) 的边所到达的点。
由于 \(p\) 所代表的所有字符串仍然是前 \(i-1\) 个字符所表示的字符串的后缀，因此在后面加上一个节点 \(s_i\) 后字符串也理应是前 \(i\) 个字符所表示的字符的后缀。
但是有可能会有从其他方向连来的边 DAG 上的边到 \(q\)，因此可能会分为两类串：
- 长度小于等于 \(len_p+1\) 的字符串，其来源一定是 \(p\) 中的字符串后面接上一个 \(s_i\) 来的。
- 长度大于 \(len_p+1\) 的字符串，其来源一定不是 \(p\) 后接上 \(s_i\)，也就是说这些串一定不是前 \(i\) 个字符所组成的串的后缀。
发现加上 \(s_i\) 之后第一类点的 edp 集合会多上 \(i\) 这个位置，而第二类点的 edp 集合保持不变，同时我们的 \(fa_u\) 一定是连向第一种情况中的字符串。因此我们需要将 \(q\) 拆成两个点来看待。特别的，如果 \(len_q\) 已经等于 \(len_p+1\)，那么无需拆点，直接 \(fa_u\gets q\) 即可。
考虑如何拆点。我们新建点 \(nq\) 表示第一类字符串所表示的点，原来的 \(q\) 表示第二类字符串所表示的点。
我们先让 \(nq\) 继承 \(q\) 的所有信息，然后根据上面有 \(len_q\gets len_p+1\)。由于原来的 \(q\) 中的所有子串共后缀且长度连续，因此第一类点的所有字符串都是第二类点的字符串的后缀，且一定是最长的能找到的后缀。因此有 \(fa_q\gets nq\)。
然后所有 \(p\) 的后缀然后走 DAG 上 \(s_i\) 这条边如果原来走到的是 \(q\)，那么现在走到的一定是 \(nq\)。如果不是 \(p\) 的后缀的，那走到的一定仍然是 \(q\)。
因此我们通过一直跳 \(fa_p\) 的方式来修改对 DAG 的影响。
然后有一些细节可能要仔细想想。比如说 edp 集合实际上是一直在变的。由于我们没有记录每个节点具体的 edp 集合长什么样，因此除了 \(q\) 节点，其他所有节点的对应的字符串的 edp 集合都是同步变动的，我们并不需要去管。
SAM 诸如此类的细节问题实际上不少，但是这里就不一一赘述了。
然后就做完了。下面是插入第 \(x\) 个字符的代码。变量名基本和上面的一致。
void insert(int x){
int u=++idcnt,p=lst,v=s[x]-'a';a[u].len=a[lst].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;}
else
{
int q=a[p].ch[v];
if(a[q].len==a[p].len+1){a[u].fa=q;}
else{
int nq=++idcnt;a[nq]=a[q];
a[nq].len=a[p].len+1,a[q].fa=a[u].fa=nq;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
}
lst=u;
}
复杂度
复杂度的话空间显然是线性的。
时间的话应要求简要叙述一下。
我们发现我么只需要证明 SAM 所包含的点数与边数都为线性即可证明 SAM 的时间复杂度为线性。
首先点数是线性的这个相对显然，因为每一次插入最多分裂出一个点来。
对于边，我们将其分开来考虑。
后缀链接显然是线性的，毕竟构成一棵树同时点数是线性的。
DAG 上可能加边的地方有两个：开始时向上跳后缀链接连边以及分裂点后向上跳后缀链接修改 DAG 上的边。
对于第一种情况，由于点数是线性的，字符集大小是常数，因此复杂度是线性的。（好像可能可以类比一下 AC 自动机？实际上均摊下来每个点都只会被修改一次，。但不管怎么说都一定是线性的。）
对于第二种情况，就比较复杂了，让我们借鉴一下 oi wiki 的思路。
我们设 \(t\) 表示 \(p\) 这个节点表示的最长的字符串，显然这是 \([1,i-1]\) 这个字符串的一个后缀。每迭代一次，\(t\) 的长度一定递减。
可以发现，在这个循环开始前，最初的 \(p\) 距离 当前的 \(lst\) 至少要经过 \(2\) 条后缀链接。
这最后一句话很难理解：在这个循环结束后，最后的 \(p'\) 对应 \(t'\)，有字符串 \(t'+s_i\) 成为路径上第二个从 \(u\) 出发的后缀链接。而在下一轮中，当前的 \(u\) 又会成为新的 \(lst\)。（好像也找不到更好的表述方式）
因此，作为当前字符串的后缀的字符串：\(link_{link_lst}\) 这个点最长的字符串，其在字符串中的位置一定单增。这样就有这个位置至多单增 \(n\) 次，也就证明了第二部分的复杂度是线性的。
最后观察到 SAM 的时空复杂度都要带一个字符集大小的系数。如果字符集过大，可以用 map 来保存 DAG 上的边，但是复杂度会多一个 \(\log\)。
线段树合并维护 edp 集合
有的时候我们的确需要使用 edp 集合来判断或维护一些东西了，怎么办呢？
我们考虑一个 edp 最初的出现可能在哪里。可以发现一定是在每次插入的新节点一定是这个 edp 第一次出现的地方。
又由于在 parent 树上的一个节点的 edp 集合是其儿子的 edp 集合的并集，因此考虑按拓扑序从下向上一次维护。
考虑用线段树直接从下向上合并。这里有两种写法。一种是可持久化线段树合并，另一种是普通线段树合并。二者在实现上的本质区别只有在合并的时候是否新建一个节点。可持久化线段树在复杂度上的唯一区别是空间复杂度是普通版的 \(2\) 倍。二者的时间复杂度都是 \(O(n\log n)\)，常数也差不多。
二者在应用上的区别是是否可以一边合并一边统计答案。如果有多测那肯定需要可持久化了。
下面是可持久化线段树合并的示例。
namespace sgt{
int ls[N<<6],rs[N<<6],tr[N<<6],idcnt=0;//可持久化一般开 30~60 倍
void modify(int &u,int l,int r,int x){
u=++idcnt;tr[u]=1;ls[u]=rs[u]=0;if(l==r)return;
int mid=(l+r)>>1;x<=mid?modify(ls[u],l,mid,x):modify(rs[u],mid+1,r,x);
}
int merge(int x,int y){
if(!x||!y)return x+y;
int u=++idcnt;tr[u]=tr[x]+tr[y];ls[u]=merge(ls[x],ls[y]),rs[u]=merge(rs[x],rs[y]);
return u;
}
int query(int u,int l,int r,int ql,int qr){//这里是查询某个节点的 edp 集合在某个区间范围内最靠右的点
if(!u||!tr[u]||qr<l||ql>r)return 0;if(l==r)return l;
int mid=(l+r)>>1,res=query(rs[u],mid+1,r,ql,qr);
return res?res:query(ls[u],l,mid,ql,qr);
}
}
应用
上面说了这么多，但是 SAM 最后只有 DAG 以及 parent 树保存了下来，而具体的 edp 集合长什么样以及每个节点对应哪些字符串之类的东西都没有，那我们算这些干什么呢？
事实上，SAM 的主要作用是提供运算的平台以及一些性质。（这就是为什么这东西更像数据结构的原因）
以洛谷上的模板题举例。
P3804 【模板】后缀自动机（edp 集合大小）
计算出现次数不为 1 的子串的出现次数乘上其长度的最大值。
这个题用了 SAM 的一个比较常见的套路，就是在 parent 树上做类似于树形 DP 的东西。
可以发现一种子串的出现次数就是其这个字符串所在的节点的 edp 集合大小。
考虑哪些节点的 edp 会包含 \(i\) 这个位置，我们找到前缀 \(i\) 对应的节点，然后从这个点一直跳到根都会包含 \(i\)，相当于链加 1。
因此我们将每个前缀的对应节点的初始大小设为 1，然后求子树和即可。发现前缀的对应节点就是每次插入节点的 \(u\)。直接做就可以了。
code
实际上很多 SAM 题掌握板子后很快就可以写出来。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+7;
string s;
int lst=1,idcnt=1,cnt[N],tot[N];long long ans=0;
vector <int> t[N];
struct node{
int fa,ch[26],len;
}a[N];
void insert(int x){
int u=++idcnt,p=lst,v=s[x]-'a';a[u].len=a[lst].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;}
else
{
int q=a[p].ch[v];
if(a[q].len==a[p].len+1){a[u].fa=q;}
else{
int nq=++idcnt;a[nq]=a[q];
a[nq].len=a[p].len+1,a[q].fa=a[u].fa=nq;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
}
cnt[u]=1;lst=u;
}
void dfs1(int u){
for(int i=0;i<tot[u];i++){
int v=t[u][i];dfs1(v);
cnt[u]+=cnt[v];
}
if(cnt[u]!=1) ans=max(1ll*ans,1ll*cnt[u]*a[u].len);
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s;int len=s.length();for(int i=0;i<len;i++) insert(i);
for(int i=1;i<=idcnt;i++) t[a[i].fa].push_back(i),tot[a[i].fa]++;
dfs1(1);cout<<ans;return 0;
}
P6139 【模板】广义后缀自动机（广义 SAM）
虽然有的题可以通过在字符串之间连边来做到同时建多个串的 SAM，但是有的时候这个分隔符会有影响，我们需要一种能够不添加额外字符的，能够接受多个串的，线性的自动机。
考虑我们只有一个串的时候是怎么做的：从左到右依次将当前节点 insert 进去，将当前插入的上一个节点设为 \(lst\)。
那如何做到多个串的呢？一个朴素的想法是每次插入一个新的字符串的时候就重新将 \(lst\) 设为初始节点 1。
实际上这种方法本身的正确性并没有问题，但是 SAM 建出来后会有一些额外的空节点，其并不会被任何 DAG 的边相连。
因为我们将 \(lst\) 设为 1 之后可能出现插入与之前完全相同的序列的操作。但是有些题这样做并不会影响正确性，因为这些空节点本身没有任何信息，一般不会被访问到。但是有些题，比如在 parent 树上 DP 可能就会有问题。（注意，这些空节点仍然会有后缀链接）
那解决这个问题的也相对朴素的想法是将所有的字符串先插入到一个 trie 树里面，去掉前缀本质相同的情况，然后一个一个插入即可。
实际上这样做也的确是正确的。我们只需要从上向下依次 bfs 整颗 trie 树，每次插入节点的时候都设当前节点的 \(lst\) 为其 trie 上的父亲即可。
那为什么不能 dfs 整个 trie 树呢？事实上，这样做也会导致与每次插入新字符串重置 \(lst\) 类似的结果，就是会产生空节点。
至于原因，具体的可以去看最开头给出的那篇讨论： 悲惨故事 长文警告 关于广义 SAM 的讨论。
如果只是做题，那只需要记住直接 bfs 就是对的。然后直接像正常的 SAM 一样 insert 即可。
最后统计答案，可以发现多串的本质不同子串个数仍然是每个节点的 \(len_u-len_{link_u}\) 之和。而要求输出节点个数是为了保证你写的不是带有空节点的错误的广义 SAM。如果你写的是正确的那这个当然是 naive 的。
code
如果要看广义 SAM 的练习题，可以去在下面翻到 P4081 [USACO17DEC] Standing Out from the Herd P 这道题的题解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+7;
ll n,fa[N],idcnt=1,triecnt=1,ch[N][26],bian[N],pos[N];ll ans=0;
string s;
struct node{int fa;ll len;int ch[26];}a[N<<1];
void add(string s) {//trie
int u=1,len=s.length();
for(int i=0;i<len;i++){
int v=s[i]-'a';if(!ch[u][v]) ch[u][v]=++triecnt,fa[triecnt]=u,bian[triecnt]=v;
u=ch[u][v];
}
}
int insert(int v,int lst){
int u=++idcnt,p=lst;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;}
else{
int q=a[p].ch[v];if(a[q].len==a[p].len+1){a[u].fa=q;}
else{
int nq=++idcnt;a[nq]=a[q];a[nq].len=a[p].len+1;a[q].fa=a[u].fa=nq;
while(p&&a[p].ch[v]==q){a[p].ch[v]=nq,p=a[p].fa;}
}
}
ans+=a[u].len-a[a[u].fa].len;
return u;
}
void bfs(){
queue <int> q;
pos[1]=1;for(int i=0;i<26;i++) if(ch[1][i]) q.push(ch[1][i]);
while(!q.empty()){
int u=q.front();q.pop();
pos[u]=insert(bian[u],pos[fa[u]]);
for(int i=0;i<26;i++)if(ch[u][i]) q.push(ch[u][i]);
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;for(int i=1;i<=n;i++) cin>>s,add(s);
bfs();cout<<ans<<'\n'<<idcnt<<'\n';
return 0;
}
P1368 【模板】最小表示法（最小循环位移）
“循环位移”的一个经典的处理办法就是将字符串翻倍拼在一起，然后将拼起来的字符串插入 SAM 里面。
由于 SAM 走 DAG 上的边可以到达所有字串，因此我们直接从根节点开始走走长度为 \(n\) 的序列就一定是原串的一种循环位移。
那显然每次尽可能走最小的边即可。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int idcnt=1,lst=1,n,s[N],cnt=0,que[N];
struct node{
int fa,len,ch[31];
}a[N];
void insert(int v){
int u=++idcnt,p=lst;a[u].len=a[p].len+1;lst=u;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;return;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1) {a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void dfs1(int u){
if(cnt>n)return;
for(int i=0;i<=30;i++){
if(a[u].ch[i]){
que[++cnt]=i;dfs1(a[u].ch[i]);return;
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;for(int i=1;i<=n;i++) cin>>s[i],insert(s[i]);for(int i=1;i<=n;i++) insert(s[i]);
dfs1(1);for(int i=1;i<=n;i++) cout<<que[i]<<' ';return 0;
}
P4070 [SDOI2016] 生成魔咒（动态插入后缀整体本质不同子串个数）
一个结论是每次插入一个后缀字符后，增加的本质不同字串个数是 \(len_u-len_{link_u}\)。具体证明不太会证明。
感性理解的话增加的本质不同的字符串一定是以当前节点结尾的字符串。而对原来 SAM 结构的修改就只可能是拆点，而拆点并不会影响本质不同子串个数。以当前节点为后缀的字符串如果原本就在 SAM 中，那其一定在所谓的 \(nq\) 节点也就是新建的拆开的节点中，而其不会对本质不同子串数造成影响。
然后 \(len_u\) 与 \(minlen_u\) 之间的所有字符串都是连续的。然后 \(len_{link_u}\) 就是 \(minlen_u-1\)，然后就是这个东西了。
然后按上面的做就可以了。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
struct node{int fa,len;map <int,int> ch;}a[N];
int n,idcnt=1,lst=1;long long ans=0;
void insert(int x){
int v=x,u=++idcnt,p=lst;lst=u;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;}
else {
int q=a[p].ch[v];
if(a[q].len==a[p].len+1){a[u].fa=q;}
else{
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
}
ans=ans+1ll*(a[u].len-a[a[u].fa].len);cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;int x;for(int i=1;i<=n;i++) cin>>x,insert(x);
return 0;
}
P3975 [TJOI2015] 弦论（本质不同/位置不同子串个数求第 k 大子串）
当然先建出 SAM。发现只要求出 SAM 上以每个节点为起点所表示的 DAG 的图的子串个数就可以找到第 k 大子串了。（类似值域线段树上找第 k 大？）
对于每个节点的子串个数，有两种统计。本质不同算一种或者位置不同算一种。
事实上两种东西是本质相同的。我们设 \(f_u\) 表示 \(u\) 这个节点开始沿着 DAG 向下走的不同子串个数。
发现如果说本质不同算一种，那对于一个点 \(u\)，\(f_u\) 就是以 \(u\) 为起点的 DAG 向下走的路径条数。容易发现这个可以树形 DP 求出来。具体而言就是初始将所有的 \(f\) 值设为 \(1\)，然后按照拓扑序以此将 \(f\) 值向 DAG 上的 “父亲” 贡献。具体实现就是写一个带访问标记的 dfs。
如果位置不同算一种，那 \(f\) 的初始值就是每个点的 edp 集合大小，毕竟 edp 集合大小就是字符串的出现次数。然后计算方法与上面一模一样，而 edp 集合大小的计算方法与模板题一模一样，这里不再赘述。
code
本来用的是自己的实现方式，但是死活过不去，主要写的有点复杂。后来看了题解换了种写法，一边找一边输出才过的。不知道为什么将字符串返回的写法没有输出。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2.5e6;
long long f[N],siz[N];
int idcnt=1,lst=1,cnt[N],tot[N],vis[N],t,k,sign=0;
struct node{int fa,len,ch[26];}a[N];
vector <int> bian[N];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';lst=u;cnt[u]=1;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;return;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1) {a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[nq].len=a[p].len+1,a[q].fa=a[u].fa=nq;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void build(){for(int i=1;i<=idcnt;i++) if(a[i].fa) bian[a[i].fa].push_back(i),tot[a[i].fa]++;}
void dfs1(int u){
for(int i=0;i<tot[u];i++){
int v=bian[u][i];dfs1(v);
cnt[u]+=1ll*cnt[v];
}
f[u]=cnt[u];
}
int dfs2(int u){
if(vis[u])return f[u];vis[u]=1;
for(int i=0;i<26;i++){
int v=a[u].ch[i];if(!v) continue;
f[u]+=dfs2(v);
}
return f[u];
}
void query(int u,int k){
if(k>f[u]){puts("-1");return ;}
if(k<=cnt[u]) {return ;}k-=cnt[u];
for(int i=0;i<26;i++){
int v=a[u].ch[i];
if(k<=f[v]) {putchar('a'+i);query(v,k);return ;}
k-=f[v];
}
}
void init(){
if(t==0){
for(int i=1;i<=idcnt;i++) f[i]=cnt[i]=1;
}
else dfs1(1);
f[1]=cnt[1]=0;
dfs2(1);
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s;cin>>s;int len=s.length();for(int i=0;i<len;i++) insert(s[i]);
cin>>t>>k;build();init();query(1,k);
return 0;
}
SP1811 LCS - Longest Common Substring（双串最长公共子串）
找两个串的最长公共子串，一个比较巧妙的思路是将 SAM 看做与 AC 自动机类似的东西，把后缀链接看成失配边。
首先对一个串建出 SAM，然后从头向后依次枚举另一个串的每个字符，假设当前枚举到的位置为 \(i\)，那找到一个尽量大的 \(tmp\) 表示考虑以 \(i\) 结尾，长度为 \(tmp\) 的子串是第一个串的子串。这里设 \(p\) 表示这个最长公共子串在 SAM 上表示的点，当前的字符是 \(t_i\)。
假设上一个点求出来的公共子串长度最大值是 \(tmp'\)，上一个公共子串在 SAM 上表示的点是 \(p'\)，那么如果 \(ch_{p',t_i}\) 不是空的，那显然直接继承上一个的公共子串是最优的，那 \(tmp\gets tmp'+1,p\gets ch_{p',t_i}\)。
如果不是，那就像 AC 自动机一样，\(p\gets fa_{p'}\)。这样做的理由是 \(fa_{p'}\) 一定是最长的可能拥有 \(t_i\) 这条出边的上一个串的后缀。这里和 AC 自动机的逻辑是类似的。
然后如果没有 \(t_i\) 这条出边，就始终令 \(p\gets fa_p\) 直到有 \(t_i\) 的出边。如果一直跳到根节点都没有那就 \(tmp\gets 0,p\gets 1\) 重新开始跳。
如果有，就令 \(tmp\gets len_p+1\)，然后再令 \(p\gets ch_{p,t_i}\)。至于逻辑可以自己画图想一想。
然后对于每一种 \(tmp\) 取 \(\max\) 即为答案。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1.5e6;
int idcnt=1,lst=1;
string t,s;
struct node{int fa,len,ch[26];}a[N];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';lst=u;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;return;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1){a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void solve(){
int len2=t.length(),p=1,ans=0,tmp=0;
for(int i=0;i<len2;i++){
int v=t[i]-'a';
if(a[p].ch[v]){tmp++;ans=max(ans,tmp);p=a[p].ch[v];continue;}
while(p&&a[p].ch[v]==0)p=a[p].fa;
if(p==0) {p=1,tmp=0;continue;}
tmp=a[p].len+1;p=a[p].ch[v];ans=max(ans,tmp);
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s>>t;int len1=s.length();for(int i=0;i<len1;i++) insert(s[i]);
solve();return 0;
}
SP1812 LCS2 - Longest Common Substring II（多串最长公共子串）
这里的考虑是一样的。我们分别对除了建出 SAM 的那个串以外的串做一遍上面的操作，但我们直接将所有答案取最大值显然不对。我们考虑在 SAM 的节点上统计答案。我们对于每种输入进来的大串，先对于枚举的每一位将其 \(tmp\) 挂在 \(p\) 上。
我们发现对于一个 SAM 上的节点 \(u\)，发现其可能的最长公共子串一定是以其为起点的 DAG 上的所有点的最大的 \(tmp\)。当然，这个值不能超过 \(len_u\)。（因为当前点表示的串一定是向下的串的前缀。做了这么多题了应该有一点感觉了）
于是拓扑一下以此取 \(\max\) 即可。然后对于每种不同的输入进来的大串，其每个节点上表示的每种串的最长公共子串长度的最小值。
然后最后在所有点的最终答案中找一个最大值即可。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int idcnt=1,lst=1,que[N],buc[N],len1,mi[N],mx[N];
struct node{
int fa,len,ch[26];
}a[N];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';lst=u,a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;return;}
int q=a[p].ch[v];if(a[p].len+1==a[q].len) {a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void solve(string s){
int p=1,tmp=0,len2=s.length();
for(int i=0;i<len2;i++){
int v=s[i]-'a';
if(a[p].ch[v]){p=a[p].ch[v];tmp++;}
else{
while(p&&a[p].ch[v]==0) p=a[p].fa;
if(!p) {p=1,tmp=0;continue;}
tmp=a[p].len+1;p=a[p].ch[v];
}
mx[p]=max(mx[p],tmp);
}
for(int i=idcnt;i>=1;i--){
int u=que[i];mx[a[u].fa]=max(mx[a[u].fa],min(mx[u],a[a[u].fa].len));
mi[u]=min(mi[u],mx[u]);mx[u]=0;
}
}
void topu(){ //非常优秀且优雅的 SAM 的 DAG 上的拓扑写法
for(int i=1;i<=idcnt;i++) buc[a[i].len]++;
for(int i=1;i<=len1;i++) buc[i]+=buc[i-1];
for(int i=idcnt;i>=1;i--) que[buc[a[i].len]--]=i; //这里顺序应该没有影响
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s;cin>>s;len1=s.length();for(int i=0;i<len1;i++) insert(s[i]);
topu();memset(mi,0x3f3f,sizeof(mi));
while(cin>>s) solve(s);
int ans=0;for(int i=1;i<=idcnt;i++) ans=max(ans,mi[i]);
cout<<ans;return 0;
}
P6640 [BJOI2020] 封印（两串区间最长公共子串）
这时难度开始上来了，需要与其他东西结合一下。
显然对于那个完整的串建出 SAM，然后仍然是求出以 \(s\) 的每一位为结尾的最长公共子串长度。
然后发现不太会做了，因为要求的东西变成了：
发现形式是最小的最大，那考虑二分答案。
考虑二分这个答案 \(ans\)，那就变成了检查对于 \(i\in [l+ans-1,r]\)，有没有 \(tmp_i\ge ans\)。因为我们枚举的这个 \(ans\) 实际上也是区间长度，因此 \([l,l+ans-2]\) 这一段产生的值一定不可能大于 \(ans\)。
那就变成了一个区间 RMQ 问题。用 st 表预处理 \(tmp\) 的最大值可以做到时空复杂度 \(O(n\log n)\)。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7,M=18;//17
string s,t;
int n,m,idcnt=1,lst=1,f[N],st[N][M],q;
struct node{
int fa,len,ch[26];
}a[N];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';a[u].len=a[p].len+1;lst=u;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;return;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1) {a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void init(){
int p=1,tmp=0;
for(int i=0;i<n;i++){
int v=s[i]-'a';
if(a[p].ch[v]){tmp++;p=a[p].ch[v];}
else{
while(p&&a[p].ch[v]==0) p=a[p].fa;
if(!p){p=1,tmp=0;continue;}
tmp=a[p].len+1;p=a[p].ch[v];
}
st[i][0]=f[i]=tmp;
}
for(int l=1;l<=17;l++){
for(int i=0;i<n;i++){
st[i][l]=max(st[i][l-1],st[i+(1<<(l-1))][l-1]);
}
}
}
int get(int l,int r){
int len=r-l+1,k=log2(len);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int l,int r,int mid){
return (get(l+mid-1,r)>=mid);
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s>>t;n=s.length(),m=t.length();for(int i=0;i<m;i++) insert(t[i]);
init();cin>>q;
while(q--){
int ql,qr,l=0,r,ans=l;cin>>ql>>qr;ql--,qr--;r=qr-ql+1;
while(l<=r){
int mid=(l+r)>>1;
if(check(ql,qr,mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<'\n';
}
return 0;
}
P4022 [CTSC2012] 熟悉的文章
上面的题可以说都是各种模板，而这种题就是具体的应用了，可能涉及到与上面东西的套娃。
同样看到最小值最大，那么还是先二分答案。
但是合法的判定要求有点奇怪：要求选出来的串的总长度 \(\ge 0.9|S|\)。这种奇怪要求只能想到 DP 去强行求解最长总长度。
设 \(dp_i\) 表示前 \(i\) 个字符所能划定出来的最长长度。注意我们这里已经二分，要求了最短的串的长度至少为 \(ans\) 了。
那有转移：
其中 \(tmp\) 表示 \(S\) 与给定的 \(m\) 个串的最长公共子串长度。这个通过将 \(m\) 个串拼接成一个串，不同串间加入特殊的分隔符，然后将整个串建出 SAM，然后与 \(S\) 求出以 \(S\) 的每一位结尾的最长公共子串求得。本质上是一个双串的最长公共子串。正确性举例易得。
然后发现上述东西有单调性，\(j\) 的限制本身是一个滑动窗口。于是单调队列优化 DP 即可。复杂度 \(O(n\log n)\)。
code
实现起来可能有点烦，毕竟套娃，还有多测。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+7;
int idcnt=1,lst=1,f[N],que[N],dp[N];
string s;
struct node{
int fa,len,ch[3];
}a[N];
void insert(int v){
int u=++idcnt,p=lst;a[u].len=a[p].len+1;lst=u;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;return;}
int q=a[p].ch[v];if(a[p].len+1==a[q].len){a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void init(){
for(int i=1;i<=idcnt;i++) a[i].fa=a[i].len=0,memset(a[i].ch,0,sizeof(a[i].ch));
idcnt=lst=1;
}
bool check(int len2){
int l=1,r=0,len1=s.length()-1;que[0]=que[1]=que[2]=0;
for(int i=0;i<len2;i++) dp[i]=0;
for(int i=len2;i<=len1;i++){
dp[i]=dp[i-1];
while(l<=r&&dp[que[r]]-que[r]<dp[i-len2]-(i-len2)) r--;
que[++r]=i-len2;while(l<=r&&que[l]<i-f[i]) l++;
if(l<=r)dp[i]=max(dp[i],dp[que[l]]+i-que[l]);
}
return (dp[len1]*10>=len1*9);
}
void calc(){
int p=1,tmp=0,len1=s.length();s=' '+s;
for(int i=1;i<=len1;i++){
int v=s[i]-'0';f[i]=que[i]=dp[i]=0;
if(a[p].ch[v]){tmp++,p=a[p].ch[v];}
else{
while(p&&a[p].ch[v]==0) p=a[p].fa;
if(!p){p=1,tmp=0;}
else tmp=a[p].len+1,p=a[p].ch[v];
}
f[i]=tmp;
}
int l=0,r=len1,ans=l;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){cin>>s;int len1=s.length();for(int j=0;j<len1;j++)insert(s[j]-'0');insert(2);}
for(int i=1;i<=n;i++){cin>>s;calc();}//init(),
return 0;
}
P2336 [SCOI2012] 喵星球上的点名（区间数颜色数）
显然先将所有的名字连在一起，中间加入分隔符。但这样没有办法区分开名和姓的区别。考虑给一个人的姓名的所有节点染上对应的颜色。
然后我们暴力在 DAG 上跳点名的串。显然如果走不到那这个点名对第一和第二问都没有意义。然后我们就可以找到这个点名的串所对应的 SAM 节点了。
然后发现第一问实际上就是求在 \(parent\) 树上每个点名的串对应的点的子树内的颜色数。
第二问实际上就是每种颜色被多少个点名的串对应的点的子树包含。
全部都与子树有关，显然考虑将 \(parent\) 树拍扁在 \(dfs\) 序上做。（然后就被这个很 naive 的东西卡了一辈子）
从左到右扫 \(dfs\) 序，挂在扫描线上直接做。可以画图感知一下这个怎么做。提高组内容就不强调了。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+7;
int n,m,idcnt=1,lst=1,col[N],tr[N],tmp[N],pre[N],dfn[N],dfncnt=0,loc[N],siz[N],ans[N];
struct node{
int fa,len;map <int,int> ch;
}a[N];
vector <int> q[N],q1[N],q2[N];
void add(int x,int w){while(x<=3*idcnt)tr[x]+=w,x+=x&-x;}
int query(int x){int res=0;while(x)res+=tr[x],x-=x&-x;return res;}
int get(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
void insert(int v){
int u=++idcnt,p=lst;lst=u;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;return;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1) {a[u].fa=q;return;}
int nq=++idcnt;a[nq]=a[q];a[q].fa=a[u].fa=nq;a[nq].len=a[p].len+1;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
void dfs1(int u){
dfn[u]=++dfncnt,loc[dfncnt]=u;siz[u]=1;
for(int v:q[u]){dfs1(v);siz[u]+=siz[v];}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=2;j++){
int num,x;cin>>num;for(int k=1;k<=num;k++){cin>>x;insert(x);col[lst]=i;}
insert(-1);
}
}
for(int i=2;i<=idcnt;i++) q[a[i].fa].push_back(i);
dfs1(1);
for(int i=1;i<=idcnt;i++){pre[i]=tmp[col[loc[i]]];tmp[col[loc[i]]]=i;}
for(int i=1;i<=m;i++){
int num,p=1,sign=0;cin>>num;
for(int j=1,x;j<=num;j++) {cin>>x;if(sign)continue;if(a[p].ch[x]==0) sign=1;else p=a[p].ch[x];}
if(sign) continue;
q1[dfn[p]+siz[p]-1].push_back(i);tmp[i]=p;
q2[dfn[p]].push_back(dfn[p]),q2[dfn[p]+siz[p]].push_back(-dfn[p]);
}
for(int i=1;i<=idcnt;i++){
if(col[loc[i]]){add(i,1);if(pre[i]>1)add(pre[i],-1);}
for(int j:q1[i]) ans[j]=get(dfn[tmp[j]],i);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n',ans[i]=0;
memset(tr,0,sizeof(tr));
for(int i=1;i<=idcnt;i++){
for(int j:q2[i]) add(abs(j),j>0?1:-1);
ans[col[loc[i]]]+=get(pre[i]+1,i);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
return 0;
}
P4081 [USACO17DEC] Standing Out from the Herd P
简要而言题意就是算每个串中没有出现在其他串中的本质不同子串个数。
显然如果一个子串要只在某个字符串里出现过，那其在 SAM 上对应的节点的 edp 集合一定只能在这个字符串里面。
那考虑一下如何维护这个东西。发现一旦一个点的 edp 集合里出现了两个不同字符串里的位置，那这个点里的所有子串一定都不能给任何一种字符串做出贡献，同时其所有在 parent 树上的祖先一定也都不能贡献。（parent 上的祖先的 edp 集合一定包含其子树里所有节点的 edp 集合）
反之，一个点的 edp 集合里的所有位置都只在一个字符串里，那么显然这个点只能对对应的字符串有 \(len_u-len_{link_u}\) 的贡献。
由于对于一个点，parent 树上的子树中有一个点出现了两个不同字符串的位置，因此直接一遍 dfs 向上合并即可。
至于给 SAM 上的点打初始的属于哪个字符串的标记，可以直接在 trie 树上打，insert 的时候将相应的标记继承下来。
code
需要注意的是，insert 的时候的拆点操作也需要将 \(q\) 节点的颜色复制给 \(nq\)。具体的东西可以看代码。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,ch[N][26],triecnt=1,fa[N],bian[N],pos[N],idcnt=1,f[N<<1],sign[N],scnt=0,ans[N];
struct node{int fa,len,ch[26];}a[N<<1];
vector <int> q[N<<1];
void add(string s){
int u=1,len=s.length();++scnt;
for(int i=0;i<len;i++){
int v=s[i]-'a';if(!ch[u][v]) ch[u][v]=++triecnt,fa[triecnt]=u,bian[triecnt]=v;
u=ch[u][v];sign[u]=sign[u]?-1:scnt;
}
}
int insert(int v,int lst){
int u=++idcnt,p=lst;a[u].len=a[p].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p){a[u].fa=1;return u;}
int q=a[p].ch[v];if(a[q].len==a[p].len+1){a[u].fa=q;return u;}
int nq=++idcnt;a[nq]=a[q];a[nq].len=a[p].len+1;a[q].fa=a[u].fa=nq;f[nq]=f[q];
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
return u;
}
void bfs(){
queue <int> q;pos[1]=1;for(int i=0;i<26;i++) if(ch[1][i])q.push(ch[1][i]);
while(!q.empty()){
int u=q.front();q.pop();
pos[u]=insert(bian[u],pos[fa[u]]),f[pos[u]]=sign[u];
for(int i=0;i<26;i++) if(ch[u][i]) q.push(ch[u][i]);
}
}
void init(){for(int i=2;i<=idcnt;i++)q[a[i].fa].push_back(i);}
void dfs(int u){
int len=q[u].size();
for(int i=0;i<len;i++){
int v=q[u][i];dfs(v);
f[u]=f[u]==f[v]?f[u]:-1;
}
if(f[u]!=-1) ans[f[u]]+=a[u].len-a[a[u].fa].len;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s;cin>>n;for(int i=1;i<=n;i++) cin>>s,add(s);
bfs();init();dfs(1);
for(int i=1;i<=scnt;i++) cout<<ans[i]<<'\n';
return 0;
}
P4770 [NOI2018] 你的名字
考虑如果询问的 \(l=1,r=|s|\) 怎么做。
首先直接对 \(s\) 和 \(t\) 建 SAM 的复杂度显然是对的。
考虑一个小 trick。我们维护对于 \(t\) 的每一个前缀，在 \(s\) 中能够匹配到的最长长度是多少。
然后发现对于 \(t\) 的 parent 树上的每一个点 \(u\)，其能够在 \(s\) 中匹配的最长长度是其子树中能匹配的最长长度与 \(len_u\) 取 \(\min\)。
因此我们只需要对于 \(t\) 的每一个前缀去求最长匹配。我们仍然把 \(s\) 的 SAM 看做对于 \(s\) 的每个子串建的 AC 自动机，然后在 \(s\) 的 SAM 上面类似的跳 \(fa\) 即可。
然后考虑统计贡献。由于对于一个 \(t\) 的 SAM 上的每一个点 \(u\)，我们都求出来了其在 \(s\) 中能匹配的最长长度，我们设为 \(dis_u\)。因此直接有
注意我们统计的是没有在 \(s\) 中出现过的本质不同子串个数。
这里的 \(dis_u\) 已经与 \(len_u\) 取过 \(\min\) 了。同时，其贡献的个数当然不能超过这个节点所代表的字符串个数，也就是 \(len_u-len_{link_u}\)。
复杂度 \(O(n)\)。
考虑对于任意的询问区间怎么做。
仍然是类似的思路，考虑在划定区间的意义下 \(dis\) 怎么求。
发现实际上是类似的。现在通过原来的求法求出来的是 \(dis\) 可能的最大值。那什么时候 \(dis\) 可能小于这个值呢？
我们通过可持久化线段树合并在 \(s\) 的 SAM 上找到划定的 \(s\) 的范围 \([l,r]\) 内当前跳到的节点的 edp 集合中最右边的位置 \(loc\)。显然这个时候的匹配最大的长度 \(tmp\) 就是 \(loc-l+1\)。
我们仍然是一直向上跳 \(fa\) 直到 \(tmp>len_{link_u}\)，因为这样才可能有贡献。然后当前的 \(dis\) 就是求出来的上界和 \(tmp,len_u\) 取个 \(\min\) 即可。计算贡献与上面一模一样。
复杂度 \(O(n\log n)\)。
code
结果线段树合并写错了调了好几个小时，要爆了。想清楚了之后其实细节都比较清晰。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+7;
int lens,lent;
string s,t;
namespace sgt{
int ls[N<<5],rs[N<<5],tr[N<<5],idcnt=0;
void modify(int &u,int l,int r,int x){
u=++idcnt;tr[u]=1;ls[u]=rs[u]=0;if(l==r)return;
int mid=(l+r)>>1;x<=mid?modify(ls[u],l,mid,x):modify(rs[u],mid+1,r,x);
}
int merge(int x,int y){
if(!x||!y)return x+y;
int u=++idcnt;tr[u]=tr[x]+tr[y];ls[u]=merge(ls[x],ls[y]),rs[u]=merge(rs[x],rs[y]);
return u;
}
int query(int u,int l,int r,int ql,int qr){
if(!u||!tr[u]||qr<l||ql>r)return 0;if(l==r)return l;
int mid=(l+r)>>1,res=query(rs[u],mid+1,r,ql,qr);
return res?res:query(ls[u],l,mid,ql,qr);
}
}
namespace sam1{
int idcnt=1,lst=1,fa[N>>1],len[N>>1],ch[N>>1][26],buc[N>>2],que[N>>1],rt[N>>1],dis[N];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';lst=u;len[u]=len[p]+1;
while(p&&ch[p][v]==0){ch[p][v]=u,p=fa[p];}
if(!p){fa[u]=1;return;}
int q=ch[p][v];if(len[q]==len[p]+1){fa[u]=q;return;}
int nq=++idcnt;len[nq]=len[p]+1;fa[nq]=fa[q];for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
fa[u]=fa[q]=nq;while(p&&ch[p][v]==q)ch[p][v]=nq,p=fa[p];
}
void build(){
for(int i=1;i<=idcnt;i++) buc[len[i]]++;
for(int i=1;i<=lens;i++) buc[i]+=buc[i-1];
for(int i=idcnt;i>=1;i--) que[buc[len[i]]--]=i;
for(int i=0,u=1;i<lens;i++) {int v=s[i]-'a';u=ch[u][v];sgt::modify(rt[u],1,lens,i+1);}//注意自己的写法，i+1！！
for(int i=idcnt;i>=2;i--){rt[fa[que[i]]]=sgt::merge(rt[fa[que[i]]],rt[que[i]]);}
}
int get(int u,int l,int r){int res=sgt::query(rt[u],1,lens,l,r);return (!res)?0:res-l+1;}//取当前 edp 限制下的最长串
void calc(int l,int r){
int u=1;dis[0]=0;
for(int i=0;i<lent;i++){
int v=t[i]-'a';
while(u>1&&ch[u][v]==0) u=fa[u];
if(ch[u][v]){
dis[i]=min(len[u]+1,dis[max(i-1,0)]+1);u=ch[u][v];//求答案上界。注意到当 u 不跳的时候答案上界即为min中后面的那一项。这里只是取了个巧。
while(u>1&&get(u,l,r)<=len[fa[u]]) u=fa[u];//最长串的长度比自己的最短串的长度还要小
if(u==1){dis[i]=0;continue;}
dis[i]=min(dis[i],min(get(u,l,r),len[u]));
}
else dis[i]=0;
}
}
}
namespace sam2{
vector <int> q[N];
int idcnt=1,lst=1,fa[N],len[N],ch[N][26],pos[N];
void init(){for(int i=1;i<=idcnt;i++)memset(ch[i],0,sizeof(ch[i])),q[i].clear(),len[i]=fa[i]=pos[i]=0;idcnt=1,lst=1,lent=t.length();}
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';lst=u;len[u]=len[p]+1;
while(p&&ch[p][v]==0){ch[p][v]=u,p=fa[p];}
if(!p){fa[u]=1;return;}
int q=ch[p][v];if(len[q]==len[p]+1){fa[u]=q;return;}
int nq=++idcnt;len[nq]=len[p]+1;fa[nq]=fa[q];for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
fa[u]=fa[q]=nq;while(p&&ch[p][v]==q)ch[p][v]=nq,p=fa[p];
}
void dfs(int u){for(int v:q[u]){dfs(v);pos[u]=max(pos[u],pos[v]);}}
void solve(){
ll ans=0;
for(int i=0,u=1;i<lent;i++){int v=t[i]-'a';u=ch[u][v];pos[u]=i;}
for(int i=2;i<=idcnt;i++) q[fa[i]].push_back(i);dfs(1);
for(int i=2;i<=idcnt;i++){
int tmp=sam1::dis[pos[i]];
if(tmp<len[fa[i]]) ans+=len[i]-len[fa[i]];else ans+=max(0,len[i]-tmp);
}
cout<<ans<<'\n';
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s;lens=s.length();for(int i=0;i<lens;i++) sam1::insert(s[i]);
sam1::build();int T;cin>>T;
while(T--){
int l,r;cin>>t>>l>>r;sam2::init();for(int i=0;i<lent;i++)sam2::insert(t[i]);
sam1::calc(l,r);sam2::solve();
}
return 0;
}
P4094 [HEOI2016/TJOI2016] 字符串
实际上比较暴力。没有理解的时候感觉很高深，其实就那样。只是因为套了个线段树合并才是黑。
我们首先将整个字符串以及询问区间翻转过来，这样就变成了求最长公共后缀。
发现答案有可二分性，即可以长的字符串可以那短的字符串一定也可以。
假设当前二分出来的长度是 \(mid\)，那我们就可以在 SAM 上找到 \(s[d-mid+1,d]\) 的对应的节点。
然后就发现实际上就是找这个字符串是否在 \(s[a,b]\) 里面出现过。实际上就是找上面找到的点的 edp 集合在 \([a+mid-1,b]\) 中有没有值。
然后就做完了。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1.2e5+7;
string s;
int n,m,lens,beg[N];
namespace sgt{
int ls[N<<6],rs[N<<6],tr[N<<6],idcnt=0;
void modify(int &u,int l,int r,int x){
u=++idcnt;tr[u]=1;ls[u]=rs[u]=0;if(l==r)return;
int mid=(l+r)>>1;x<=mid?modify(ls[u],l,mid,x):modify(rs[u],mid+1,r,x);
}
int merge(int x,int y){
if(!x||!y)return x+y;
int u=++idcnt;tr[u]=tr[x]+tr[y];ls[u]=merge(ls[x],ls[y]),rs[u]=merge(rs[x],rs[y]);
return u;
}
int query(int u,int l,int r,int ql,int qr){
if(!u||!tr[u]||qr<l||ql>r)return 0;if(l==r)return l;
int mid=(l+r)>>1,res=query(rs[u],mid+1,r,ql,qr);
return res?res:query(ls[u],l,mid,ql,qr);
}
}
namespace sam{
vector <int> q[N<<1];
int idcnt=1,lst=1,f[N<<1][20],rt[N<<1];
struct node{int fa,len,ch[26];}a[N<<1];
void insert(char x){
int u=++idcnt,p=lst,v=x-'a';a[u].len=a[lst].len+1;
while(p&&a[p].ch[v]==0) a[p].ch[v]=u,p=a[p].fa;
if(!p) {a[u].fa=1;}
else
{
int q=a[p].ch[v];
if(a[q].len==a[p].len+1){a[u].fa=q;}
else{
int nq=++idcnt;a[nq]=a[q];
a[nq].len=a[p].len+1,a[q].fa=a[u].fa=nq;
while(p&&a[p].ch[v]==q) a[p].ch[v]=nq,p=a[p].fa;
}
}
lst=u;
}
void build(){for(int i=2;i<=idcnt;i++) q[a[i].fa].push_back(i);}
void dfs(int u){
f[u][0]=a[u].fa;for(int i=1;i<=17;i++) f[u][i]=f[f[u][i-1]][i-1];
for(int v:q[u]){dfs(v);}rt[a[u].fa]=sgt::merge(rt[u],rt[a[u].fa]);
}
}
bool check(int len,int a,int b,int d){
int u=beg[d-1];for(int i=17;i>=0;i--){if(sam::f[u][i]&&sam::a[sam::f[u][i]].len>=len) u=sam::f[u][i];}
return sgt::query(sam::rt[u],1,n,a+len-1,b);
}
void solve(){
int a,b,c,d;cin>>a>>b>>c>>d;a=n-a+1,b=n-b+1,c=n-c+1,d=n-d+1;swap(a,b),swap(c,d);
int l=0,r=min(b-a+1,d-c+1),ans=0;
while(l<=r){int mid=(l+r)>>1;if(check(mid,a,b,d)) l=mid+1,ans=mid;else r=mid-1;}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;cin>>s;for(int i=0;i<n/2;i++)swap(s[i],s[n-i-1]);
for(int i=0;i<n;i++) sam::insert(s[i]),sgt::modify(sam::rt[sam::lst],1,n,i+1),beg[i]=sam::lst;
sam::build();sam::dfs(1);
while(m--){solve();}
return 0;
}
P5576 [CmdOI2019] 口头禅
不得不说这个题是真的牛。%%%出题人。
首先这个题一看就比较有 lxl 的风格，考虑一下扫描线的做法。
然后就考虑一个小时不会了。主要问题是如何快速定位可以回答询问的最深节点。只能看题解了。
然后发现自己很呆。实际上自己的思路可能更接近于官方题解的第三种做法。
这种做法是基于一个观察：显然先给广义 SAM 上的所有点染相应颜色，维护每个点的连续颜色段。按照字符串长度从下向上合并颜色段，第一个合并区间能够覆盖询问的区间的点的长度就是答案。
于是考虑如何对于每个点去维护颜色段。显然线段树和平衡树都能做。但此题略卡空间，因此线段树合并不太好。而平衡树不如优雅的 set 。通过类似于颜色段均摊一样的东西，就可以维护了。当然，这个颜色段是没有权值和编号的，因此还要简单一点。
然后考虑如何查询。发现合并的时候只有当合并出新区间的时候才可能可以回答询问。因此我们现在知道了我们可以更新的询问区间，能够被回答的询问的左右端点都在这个合并出来的新区间里。
考虑将询问挂在左端点，用线段树去维护询问。线段树维护区间最小值，这样可以找到是否有询问的右端点在合并出的区间。由于我们是按节点的长度以此向上合并的，因此后面有的节点也可以贡献这个询问的时候一定不优，因此回答一个询问后就可以直接把这个询问删了。
然后做完了。set 的合并的复杂度是 \(n\log^2 n\) 的，线段树的查询同理。空间复杂度线性。
code
这道题就是显然的口胡、讲起来很爽，写起来火葬场的典例。太难写了，太久没写过颜色段均摊了，细节一车。结果直到现在都还被卡着。
口胡
可能是一些过于简单/困难的题？
P3763 [TJOI2017] DNA
首先预处理出 \(s,t\) 中的每一种前缀在 \(s\) 的 SAM 里面对应的节点。然后对于 \(s\) 的每一个前缀，求与 \(t\) 其的 \(lcs\)。如果长度不是 \(|t|\)，那么就在 \(t\) 上向前跳一个，接着求，直到次数大于 \(3\) 了或者长度为 \(|t|\) 了，直接统计答案即可。
SP8222 NSUBSTR - Substrings
显然从小往大看这个答案序列是不升的，因为短的出现次数不可能严格小于长的出现次数。于是对于 SAM 上的每一个节点维护 edp 集合大小，修改其最大长度的出现次数，最后答案就是一个后缀最大值。
P4248 [AHOI2013] 差异
和式中求链的长度是 naive 的。考虑计算后缀的 \(lcp\) 。显然将序列反过来变成求前缀的 \(lcs\)。由于两个前缀的 \(lcs\) 就是在 parent 树上的 \(lca\)，因此考虑在 \(lca\) 处统计答案。
发现是好算的。直接弄一个子树中属于主链的节点数，然后类似于点分治一样扫一遍每个子树即可。
P3181 [HAOI2016] 找相同字符
这个东西可能后缀数组直接双指针扫好做的多？
当然 SAM 也很好做。直接建广义 SAM 然后判断是否同时在两个字符串里出现过即可。具体就是树上祖先染颜色，dfs 即可。好像是上面一道题的绝对弱化版。
P1117 [NOI2016] 优秀的拆分
不是哥们 \(n^2\) 分给那么多哪个人写正解？
设 \(a_i\) 表示以 \(i\) 开头的形如 \(AA\) 串的个数，\(b_i\) 表示形式类似的以 \(i\) 结尾的串的个数。考虑答案就是 \(a_{i+1}b_i\)。
考虑如何快速求两个东西。我们设循环节的长度为 \(x\)，那么发现间隔着 \(x\) 去统计区间答案是调和级数的复杂度。
我们设枚举的区间 \([l,r],r=l+x-1\)。我们计算这段区间内的可以作为分界点的字符的个数。我们去求 \(lcp(l-1,r-1)\) 以及 \(lcs(l,r)\)，通过这个来统计答案。
P2178 [NOI2015] 品酒大会
仍然是反过来求后缀。
显然答案序列与上面一道题是类似的，单调不升的，因为长的大短的一定也大。
考虑线段树合并维护每个节点中 edp 集合中节点的最大、次大值，同样是更新最长长度的答案，最后答案序列的每个位置的答案就是后缀最大值。
（可能并不需要线段树合并？直接向上合并更新最大次大值应该也可以）
一些小 trick/想法
多串查多串的区间可以直接可持久化线段树合并。
注意区间数颜色的运用。
最长公共前缀可以把串翻转变成最长公共后缀，然后就是 parent 树上的 lca。某些时候可能和支配对相关。可以 LCT 在线维护支配对。
最值中套最值直接二分答案。
一个字符串的循环等价于 \(s[l,r-len]=s[l+len,r]\)，其中 \(len\) 是循环节的长度。
长度大于 \(\sqrt n\) 的串可以直接暴力匹配，吗？怎么做？
注意 DP 数组间字符串的承接，可能会有单调性一类的东西。
对于一些与 parent 树上链查询有关的东西，我们可以树剖然后把询问拆到重链上离线下来扫描线。
用 LCT 维护树上颜色段均摊，\(O(n\log n)\)。
