HDU-5853 Jong Hyok and String (广义后缀自动机)
题意：给定一些串，每次查询一个串，求所有的 (在所有串中\(endpos\)都与它相同的)，(出现在给定串的)不同子串个数
广义后缀自动机？
是不是听起来很高大上？
博主当然不明白原理，但是mo有关系
对于处理多个串的子串问题，把每个串都加入同一个自动机，就能得到广义后缀自动机(?)
这种容易出现重复节点的问题，不建议写
有两种解决重复节点的办法：先将串插入\(trie\)树，再在\(trie\)树上广搜建\(SAM\)
也可以在插入函数内部直接特判掉
void Extend(int c) {
int p=lst;
if(trans[p][c]) {
int q=trans[p][c];
if(len[q]==len[p]+1) lst=q;
else {
int clone=++stcnt;
memcpy(trans[clone],trans[q],sizeof trans[q]);
len[clone]=len[p]+1;
link[clone]=link[q];
while(~p && trans[p][c]==q) trans[p][c]=clone,p=link[p];
lst=link[q]=clone;
}
return;
}
int cur=++stcnt;
len[cur]=len[p]+1;
while(~p && !trans[p][c]) trans[p][c]=cur,p=link[p];
if(p==-1) link[cur]=0;
else {
int q=trans[p][c];
if(len[q]==len[p]+1) link[cur]=q;
else {
int clone=++stcnt;
memcpy(trans[clone],trans[q],sizeof trans[q]);
len[clone]=len[p]+1;
link[clone]=link[q];
while(~p && trans[p][c]==q) trans[p][c]=clone,p=link[p];
link[cur]=link[q]=clone;
}
}
lst=cur;
}
如果你愿意听队爷讲解：参考文献-2015集训队论文 提取码：6f4u
\[\
\]
构造广义后缀自动机后
实际上就是求给定串在原串中对应的状态包含的子串个数
代码里是建\(trie\)树版的
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
using namespace std;
#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template<class T=int> T rd(){
T s=0;
int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=2e5+10;
bool be;
int n,m;
char s[N/2];
int trans[N][26],link[N],len[N],stcnt,lst;
int trie[N/2][26],cnt;
void Insert(char *s){
int now=0,len=strlen(s+1);
rep(i,1,len) {
int c=s[i]-'a';
if(!trie[now][c]) trie[now][c]=++cnt;
now=trie[now][c];
}
}
void Init(){
link[0]=-1,len[0]=0;
rep(i,0,stcnt) rep(j,0,25) trans[i][j]=0;
rep(i,0,cnt) rep(j,0,25) trie[i][j]=0;
stcnt=lst=cnt=0;
}
void Extend(int c) {
int p=lst,cur=++stcnt;
len[cur]=len[p]+1;
while(~p && !trans[p][c]) trans[p][c]=cur,p=link[p];
if(p==-1) link[cur]=0;
else {
int q=trans[p][c];
if(len[q]==len[p]+1) link[cur]=q;
else {
int clone=++stcnt;
memcpy(trans[clone],trans[q],104);
len[clone]=len[p]+1;
link[clone]=link[q];
while(~p && trans[p][c]==q) trans[p][c]=clone,p=link[p];
link[cur]=link[q]=clone;
}
}
lst=cur;
}
typedef pair<int,int> Pii;
queue <Pii> que;
void Construct(){
que.push((Pii){0,0});
while(!que.empty()) {
Pii u=que.front(); que.pop();
rep(i,0,25) if(trie[u.first][i]) { // 先构造trie树
lst=u.second;
Extend(i);
que.push((Pii){trie[u.first][i],lst});
}
}
}
bool ed;
int main(){
rep(kase,1,rd()) {
n=rd(),m=rd();
Init();
rep(i,1,n) {
scanf("%s",s+1);
Insert(s);
}
Construct();
printf("Case #%d:\n",kase);
rep(i,1,m) {
scanf("%s",s+1);
int p=0,len=strlen(s+1);
rep(j,1,len) {
p=trans[p][s[j]-'a'];
if(!p) break;
}
if(!p) puts("0");
else printf("%d\n",::len[p]-::len[link[p]]);
}
}
}