题目大意
给定文本串$S$和若干模式串$\{T\}$, 对每个模式串$T$, 询问$T$是否为$S$的子串.
Solution
裸的AC自动机, 也可以用后缀数组做.
P.S. 这题数据很弱, 朴素的字符串匹配也能过.
Pitfalls
模式串有重复的. 这样, 在建TRIE时就不能直接对每个模式串对应的节点 (尾节点) 标记上模式串的序号, 否则对于重复出现的模式串, 最后一次出现的那个会把在它之前的那些覆盖掉.
正确的做法是, 对于每个尾节点作唯一标号. 另外维护一个表$idx[]$, $idx[i]$表示第$i$个模式串的尾节点的标号.
另外要注意AC自动机的某些易错的实现细节, 代码注释有提及.
Implementation
注释比较详细, 可作为模板.
#include <bits/stdc++.h>
using namespace std; const int N{<<}, M{<<}; bool res[M];
int idx[M];
char s[N], t[M];
int ch[N][], id[N], fail[N], last[N]; int get_id(char ch){
return islower(ch)?ch-'a':ch-'A'+;
} queue<int> que; int main(){
// cout<<int('a')<<' '<<int('z')<<' '<<int('A')<<' '<<int('Z')<<endl;
int T;
for(cin>>T; T--; ){
int q;
scanf("%s%d", s, &q);
int tail=; memset(res, false, sizeof(res)); //error-prone memset(ch[tail], , sizeof(ch[tail]));
tail++; for(int i=; i<=q; i++){
scanf("%s", t);
int u=;
for(int j=; t[j]; j++){
int &v=ch[u][get_id(t[j])];
if(!v){
v=tail++;
memset(ch[v], , sizeof(ch[v]));
id[v]=;
}
u=v;
}
if(!id[u]) id[u]=i; //error-prone: possibly duplicate patterns
idx[i]=id[u];
} for(int i=; i<; i++){
int u=ch[][i];
if(u){
que.push(u);
fail[u]=last[u]=; //error-prone, must be initialized!!
}
} for(; que.size(); ){
int u=que.front();
que.pop();
for(int i=; i<; i++){
//!view a variable (object) as an entity
int &v=ch[u][i];
if(v){ //v is a new node, construct a new node of AC automata
que.push(v);
//no need to init. last[] and fail[], as they are is induced.
fail[v]=ch[fail[u]][i];
last[v]=id[fail[v]]?fail[v]:last[fail[v]];
}
else{ //the expected node v does not exist
v=ch[fail[u]][i];
}
}
} for(int i=, u=; s[i]; i++){
u=ch[u][get_id(s[i])];
res[id[u]]=true;
for(int v=last[u]; v; res[id[v]]=true, v=last[v]); //error-prone
} for(int i=; i<=q; i++)
puts(res[idx[i]]?"y":"n"); }
}
UPD
上面代码中第76行
for(int v=last[u]; v; res[id[v]]=true, v=last[v]);
可优化为
for(int v=last[u]; v && !res[id[v]]; res[id[v]]=true, v=last[v]);
这样可保证每个单词节点（dictionary node）通过last指针（dictionary suffix link) 的访问次数为至多为1 ，从而提高时间效率。
上穷碧落下黄泉.