HDU 2222 Keywords Search [AC自动机]-白红宇

HDU 2222 Keywords Search [AC自动机]

阅读量：5092 次

发布时间：2019-06-13

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

题意：给一堆模式串和一个文本串，问有多少个模式串在文本串中出现过。

AC自动机，在统计答案的时候记得将end清零就好

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               using namespace std;#define rep(i,f,t) for(int i = (f), _end = (t); i <= _end; ++i)#define dep(i,f,t) for(int i = (f), _end = (t); i >= _end; --i)#define clr(c,x) memset(c,x,sizeof(c));#define debug(x) cout<<"debug "<
                
                 <

Q; int u = 0; rep(c,0,25){ if(next[0][c]){ Q.push(next[0][c]); } } while(!Q.empty()){ u = Q.front(); Q.pop(); int fu = fail[u]; rep(c,0,25){ int v = next[u][c]; if(v){ Q.push(v); fail[v] = next[fu][c]; }else{ next[u][c] = next[fu][c]; } } } } int query(char *s){ int u = 0; int ans = 0; while(*s){ int nid = *s++ - 'a'; u = next[u][nid]; int k = u; while(k){ if(end[k]){ ans += end[k]; end[k] = 0; } k = fail[k]; } } return ans; }}ac;char str[1000009];int main(){ Rush{ ac.init(); int n; scanf("%d",&n); while(n--){ scanf("%s",str); ac.insert(str); } ac.build(); scanf("%s",str); printf("%d\n",ac.query(str)); } return 0;}

转载于:https://www.cnblogs.com/DSChan/p/4861972.html

你可能感兴趣的文章