目录
题意思路时间复杂度分析实现
题意
给定一个字符串集，询问某个字符串包含哪些字符串集中的字符串。 链接：link。
思路
多模式匹配问题可以用AC自动机解决，AC自动机算法如下：
首先建立一颗字典树。再利用BFS建立fail指针（指向那个最长后缀的浅层节点），建立fail指针的方式如下：节点u的第i个孩子的fail指针，应该指向节点fail[u]的第i个孩子节点，如果为空，则继续迭代地寻找fail指针，直到fail指针为空，或找到符合条件的节点，如果最终fail指针为空，则令当前的fail为root。匹配时，先按照next往下匹配，如果next指针为空，则按照fail指针向上迭代，直到fail指针为空，或者next不为空，如果最终fail指针为空，则当前节点跳到根节点，继续下一次匹配，否则，按fail指针查找所有的后缀是否存在字符集中。
时间复杂度分析
建树的时间复杂度为
O
(
∑
i
=
1
n
L
i
)
\mathcal{O}(\sum_{i=1}^{n} L_{i})
O(∑i=1nLi)，其中
L
i
L_{i}
Li表示字符集中第
i
i
i个字符串的长度。 查找的时间复杂度为
O
(
L
)
\mathcal{O}(L)
O(L)，
L
L
L表示匹配串的长度（因为fail指针只会往浅层节点走，所以时间复杂度最多为
O
(
2
×
L
)
\mathcal{O}(2 \times L)
O(2×L)）。
实现
#include<cstdio>
#include<queue>
using namespace std
;
const int MAXN
=1e6+5;
struct Node
{
int cnt
;
Node
*fail
,*next
[26];
Node(){
cnt
=0;
fail
=nullptr;
for(int i
=0;i
<26;i
++) next
[i
]=nullptr;
};
};
char s
[MAXN
];
void build_trie(Node
*root
,const char *keyword
){
Node
*p
=root
;
for(int i
=0;keyword
[i
];i
++){
int v
=keyword
[i
]-'a';
if(p
->next
[v
]==nullptr) p
->next
[v
]=new Node
;
p
=p
->next
[v
];
}
p
->cnt
++;
}
void build_AC_automation(Node
*root
){
queue
<Node
*> que
;
que
.push(root
);
while(!que
.empty()){
Node
*cur
=que
.front();que
.pop();
for(int i
=0;i
<26;i
++){
if(cur
->next
[i
]!=nullptr){
Node
*p
=cur
->fail
;
while(p
!=nullptr){
if(p
->next
[i
]!=nullptr){
cur
->next
[i
]->fail
=p
->next
[i
];
break;
}
p
=p
->fail
;
}
if(p
==nullptr) cur
->next
[i
]->fail
=root
;
que
.push(cur
->next
[i
]);
}
}
}
}
int match(Node
*root
){
int cnt
=0;
Node
*p
=root
;
for(int i
=0;s
[i
];i
++){
int v
=s
[i
]-'a';
while(p
!=nullptr&&p
->next
[v
]==nullptr) p
=p
->fail
;
if(p
==nullptr){
p
=root
;
continue;
}
p
=p
->next
[v
];
Node
*tmp
=p
;
while(tmp
!=root
){
if(tmp
->cnt
){
cnt
+=tmp
->cnt
;
tmp
->cnt
=0;
}
else break;
tmp
=tmp
->fail
;
}
}
return cnt
;
}
void delete_trie(Node
*root
){
queue
<Node
*> que
;
que
.push(root
);
while(!que
.empty()){
Node
*cur
=que
.front();
que
.pop();
for(int i
=0;i
<26;i
++){
if(cur
->next
[i
]!=nullptr){
que
.push(cur
->next
[i
]);
}
}
delete cur
;
}
}
int main(){
int T
;scanf("%d",&T
);
while(T
--){
Node
*root
=new Node
;
int n
;scanf("%d",&n
);
for(int i
=0;i
<n
;i
++){
char keyword
[55];
scanf("\n%s",keyword
);
build_trie(root
,keyword
);
}
build_AC_automation(root
);
scanf("\n%s",s
);
printf("%d\n",match(root
));
delete_trie(root
);
}
return 0;
}
