https://www.luogu.org/problemnew/show/P3808
这是一道简单的 AC 自动机模板题.
用于检测正确性以及算法常数.
为了防止卡 OJ, 在保证正确的基础上只有两组数据, 请不要恶意提交.
管理员提示: 本题数据内有重复的单词, 且重复单词应该计算多次, 请各位注意
题目描述
给定 n 个模式串和 1 个文本串, 求有多少个模式串在文本串里出现过.
输入输出格式
输入格式:
第一行一个 n, 表示模式串个数;
下面 n 行每行一个模式串;
下面一行一个文本串.
输出格式:
一个数表示答案
输入输出样例
输入样例 #1 2 a aa aa
输出样例 #1
2
说明
subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;
参考博客: http://www.cnblogs.com/cjyyb/p/7196308.html
听说有一种需要用 trie 树做, trie 图不能做的题目?? 先 mark 下
关于失配指针的描述: 从当前节点开始, 沿着其父节点的失配指针不断向上跑, 直到到达一个节点, 它的儿子中有当前字母, 然后把这两个一样的字母连起来.
首先要构建 trie 图, 然后 fail 是在 trie 图上实现的, 所以 fail 上的跳转是在模式串上的跳转, 通过这样的跳转, 可以快速找到相匹配的模式串
- #include<bits/stdc++.h>
- using namespace std;
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define sqr(x) ((x)*(x))
- #define maxn 1000005
- typedef long long ll;
- typedef unsigned long long ull;
- const ull MOD=257;
- /*#ifndef ONLINE_JUDGE
- freopen("1.txt","r",stdin);
- #endif */
- struct tree{
- int fail;
- int vis[26];
- int num;
- }ac[1000005];
- int cnt=0;
- void build(string s){/// 建 trie 树
- int len=s.length();
- int now=0;
- for(int i=0;i<len;i++){
- if(ac[now].vis[s[i]-'a']==0){
- ac[now].vis[s[i]-'a']=++cnt;
- }
- now=ac[now].vis[s[i]-'a'];
- }
- ac[now].num+=1;
- }
- void get_fail(){/// 构建成 trie 图
- queue<int>Q;
- for(int i=0;i<26;i++){
- if(ac[0].vis[i]){
- ac[ac[0].vis[i]].fail=0;
- Q.push(ac[0].vis[i]);
- }
- }
- while(!Q.empty()){
- int u=Q.front();
- Q.pop();
- for(int i=0;i<26;i++){
- if(ac[u].vis[i]){
- ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i];
- Q.push(ac[u].vis[i]);
- }
- else{
- ac[u].vis[i]=ac[ac[u].fail].vis[i];/// 如果当前结点不存在, 就指向父亲结点的 fail 指向的结点的子结点
- }
- }
- }
- }
- int ac_query(string s){
- int len=s.length();
- int now=0,ans=0;
- for(int i=0;i<len;i++){
- now=ac[now].vis[s[i]-'a'];
- for(int t=now;t&&ac[t].num!=-1;t=ac[t].fail){
- ans+=ac[t].num;
- ac[t].num=-1;
- }
- }
- return ans;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- // freopen("1.txt","r",stdin);
- #endif
- //std::iOS::sync_with_stdio(false);
- string s;
- int n;
- cin>>n;
- for(int i=0;i<n;i++){
- cin>>s;
- build(s);
- }
- ac[0].fail=0;
- get_fail();
- cin>>s;
- cout<<ac_query(s)<<endl;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2950892.html