首页 > 其他 > 详细

ac自动机

时间:2020-02-23 18:38:15      阅读:46      评论:0      收藏:0      [点我收藏+]
//2020 1 21&2020 2 16 
#include<bits/stdc++.h>
#include<queue>
#define LETTER 26
using namespace std;
struct Trie{
    int num,match,fail; //num当此节点为终止节点时数值为一,match指距这个点最近的终止节点的编号,fail同kmp 
    int next[LETTER];//指在trie树中此节点的某字母边指向的节点 
}pool[500001];
Trie* const trie=pool + 1; //trie就是pool,统一将下标减一(有-1下标) 
int cnt;
void init(){
    cnt=0;
    memset(pool, 0,2*sizeof(Trie));
    trie[0].fail=-1; 
}
queue<int> q; 
void build() //构建trie树,过程维护队列中的节点都已处理完成match与fail 
{
  q.push(0);
  while (!q.empty()){
    int t=q.front(); 
    q.pop();
    for (int i=0;i<LETTER;i++){
      int &cur=trie[t].next[i];
      if (cur){
        q.push(cur);
        trie[cur].fail=trie[trie[t].fail].next[i];
        trie[cur].match=trie[cur].num!=0 ? cur : trie[trie[cur].fail].match;   //当这个点为终止节点时,返回自己,否则返回fail的match 
      }
      else cur=trie[trie[t].fail].next[i]; //如此点无i边,则i边指向fail的i边,fail肯定比此节点浅故按bfs搜索顺序必定以处理完成 
    }
  }
}
int search(string s)
{
    int ret=0, cur=0;
    for (int i=0;s[i];i++){
        cur=trie[cur].next[s[i]-'a'];
        for (int temp=trie[cur].match;temp>0;temp=trie[trie[temp].fail].match){ //反复横跳寻找终止节点 
            ret += trie[temp].num;
        }
            
    }
    return ret;
}
string str,st[100007];
int main()
{
    int n;
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        cin>>st[i];
        int len=st[i].size()-1;
        int last=0;
        for(int j=0;j<=len;++j){
            if(trie[last].next[int(st[i][j]-'a')]==0){
                trie[last].next[int(st[i][j]-'a')]=++cnt;
                last=cnt;
            }
            else last=trie[last].next[int(st[i][j]-'a')];
            if(j==len){
                 trie[last].num=1;
            }
        }
    }
    build();
    /* 
    for(int i=0;i<=cnt;i++){
        cout<<"No."<<i<<" failed:"<<trie[i].fail<<" match:"<<trie[i].match<<" num:"<<trie[i].num<<" "<<trie[i].next[0]<<endl;
    } 
    */
    cin>>str;
    cout<<search(str)<<endl;
    return 0;
}
/*
注:
此代码用于求 所有的模式串在主串中出现的总共次数 
*/
/*
3
aabaa
aaa
aba

aaabaa
----------
3
*/

ac自动机

原文:https://www.cnblogs.com/XJack/p/12351060.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!