AC自动机(转载)-白红宇

AC自动机(转载)

阅读量：4922 次

发布时间：2019-06-11

本文共 1397 字，大约阅读时间需要 4 分钟。

本来以为是很高级的算法其实理解以后并不难只是在字典树的基础上用fail数组标记一下回朔的位置加速查找就可以实现多模式串的匹配查找

模版如下:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    #define ll long long intusing namespace std;inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}int moth[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31};int dir[4][2]={ 1,0 ,0,1 ,-1,0 ,0,-1};int dirs[8][2]={ 1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};const int inf=0x3f3f3f3f;const ll mod=1e9+7;struct Trie{ int trie[500007][26],fail[500007],cntword[500007]; int sz,root; int newnode(){ for(int i=0;i<26;i++) trie[sz][i]=-1; cntword[sz++]=0; return sz-1; } void init(){ //初始化 sz=0; root=newnode(); } void insert(string s){ // 构建字典树 int len=s.length(); int now=root; for(int i=0;i

q; fail[root]=root; for(int i=0;i<26;i++){ if(trie[root][i]==-1) trie[root][i]=root; else{ fail[trie[root][i]]=root; q.push(trie[root][i]); } } while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0;i<26;i++){ if(trie[now][i]==-1) trie[now][i]=trie[fail[now]][i]; else{ fail[trie[now][i]]=trie[fail[now]][i]; q.push(trie[now][i]); } } } } int query(string s){ //查询操作 int len=s.length(); int now=root; int res=0; for(int i=0;i

转载于:https://www.cnblogs.com/wmj6/p/10828148.html

你可能感兴趣的文章