众所周知AC自动机和广义SAM都可以用来解决多串匹配问题。我曾经一度以为广义SAM无法替代AC自动机。而且U群也这么说过。当时U群说的是“阿狸的打字机有SAM做法了嘛？”
然而还真有2333
首先说AC自动机和广义SAM做多串匹配的原理。
它们都可以解决多个模式串在一个文本串中的匹配问题。（AC自动机模板题是询问每个串模式串在文本串中各出现几次）
做法都是先把所有模式串建出自动机，然后用文本串在上面运行。然后每次把以 为结尾的所有串（前缀 的所有后缀）的贡献根据树形结构统计上，最后得到答案。
而AC自动机在运行过程中所在的节点是最长的类似"border"的结构，广义SAM就是最长公共子串了。然而一个模式串在文本串中出现的条件就是最长“border”长度与最长公共子串长度都等于串长，于是它们都可以做匹配问题。而且AC自动机还可以做“每个模式串的前缀在文本串中出现次数”的问题。因为trie树上有所有串前缀的信息。相应的，因为SAM中存有所有子串的信息（所有的子串都有对应的节点），所以它大概也可以做“每个模式串的子串在文本串中出现次数”的问题。
其实我们可以发现，AC自动机中存储的信息无非就是每个模式串的前缀对应节点、fail边。然而这些信息在SAM上都有对应。前缀也可以找到对应节点，fail边也就是par边。所以SAM基本可以干AC自动机的所有事情了。
然后讨论一些细节：每个串前缀一定是所在状态的mxlen。因为不可能有一个串endpos与它相同且更长了。
所以我们在一些AC自动机问题上运用SAM的话，在SAM上运行文本串时要记录当前匹配长度（求最长公共子串时的操作）。如果当前匹配长度就是所在节点mxlen，那么这个节点也可以贡献到。否则（因为我们只关注前缀，而前缀都是mxlen），所以我们贡献到它父亲上即可。
还有，AC自动机还可以处理一些dp问题，其实SAM也可以的。可能你会觉得我们在运行的时候还需要记录当前匹配长度啊，那不是两维状态了么？有一个结论：一个状态走一个转移边mxlen至少加1。这是显然的。于是我们发现如果当前不满足“当前匹配长度就是所在节点mxlen”，那么再转移也依旧不会满足。于是只要记录两维状态：f[i][0/1]表示当前在第 个节点，是否满足那个条件。预处理转移就像建AC自动机一样bfs即可。于是发现用SAM跑dp常数会乘 。因为节点数乘2，还要多记状态。这也是一个比AC自动机劣的地方。
而且AC自动机有一个硬伤：当字符集大的时候它是没有什么科学的处理办法的。众多周知建AC自动机的一个科学做法是建trie图。然而建trie图需要对每个点都遍历一下字符集。而不建trie图的话找fail边又需要暴力跳fail。在字符集达到 时这都是 的。所以现在可以发现阿狸的打字机反而可以加强卡掉AC自动机。
而SAM大概唯一能卡的地方就在于它空间 倍。如果卡空间，那么大概就只能写AC自动机了。。。
最后贴一个用广义SAM写的AC自动机板子
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=4e5+50,M=2e6+50;
int n,cnt=1,p[N],lst,mxlen[N],par[N],trans[N][26],num[N];char s[M];
vector<int>v[N];
void extend(int c){
int p=lst,cur=0;
if(!trans[p][c])cur=++cnt,mxlen[cur]=mxlen[p]+1;
for(;p&&!trans[p][c];p=par[p])trans[p][c]=cur;
if(!p)par[cur]=1;
else{
int q=trans[p][c];
if(mxlen[q]==mxlen[p]+1)cur?par[cur]=q:cur=q;
else{
int nq=++cnt;
memcpy(trans[nq],trans[q],sizeof(trans[q]));
mxlen[nq]=mxlen[p]+1;par[nq]=par[q];
par[q]=nq;cur?par[cur]=nq:cur=nq;
for(;p&&trans[p][c]==q;p=par[p])trans[p][c]=nq;
}
}
lst=cur;
}
void dfs(int x){
for(int i=0,y;i<v[x].size();i++)
dfs(y=v[x][i]),num[x]+=num[y];
}
int main(){
scanf("%d",&n);
for(int i=1,ll;i<=n;i++){
scanf("%s",s+1);lst=1;
for(int j=1;s[j];j++)extend(s[j]-'a');
p[i]=lst;
}
for(int i=1;i<=cnt;i++)v[par[i]].pb(i);
scanf("%s",s+1);int len=strlen(s+1);
for(int i=1,p=1,fl=1,y;i<=len;i++){
int c=s[i]-'a';
while(p!=1&&!trans[p][c])p=par[p],fl=1;
if((y=trans[p][c]))mxlen[y]!=mxlen[p]+1?fl=0:0,p=y;
num[fl?p:par[p]]++;
}
dfs(1);
for(int i=1;i<=n;i++)printf("%d\n",num[p[i]]);
return 0;
}