HDU 2222 Keywords Search（AC自己主动机模板题）-白红宇

HDU 2222 Keywords Search（AC自己主动机模板题）

阅读量：6348 次

发布时间：2019-06-22

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

题意：给出一个字符串和若干个模板，求出在文本串中出现的模板个数。

思路：由于有可能有反复的模板，trie树权值记录每一个模板出现的次数就可以。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #define eps 1e-6#define LL long long#define pii (pair
                   
                    )//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const int maxn = 1000000 + 100;const int SIGMA_SIZE = 26;const int maxnode = 1000000+100;int n, ans;bool vis[maxn];map
                    
                      ms;int ch[maxnode][SIGMA_SIZE+5]; int val[maxnode]; int idx(char c) {return c - 'a';}struct Trie { int sz; Trie() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); memset(vis, 0, sizeof(vis)); } void insert(char *s) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++) { int c = idx(s[i]); if(!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u]++; } }; //ac自己主动机int last[maxn], f[maxn];void print(int j) { if(j && !vis[j]) { ans += val[j]; vis[j] = 1; print(last[j]); }} int getFail() { queue
                     
                       q; f[0] = 0; for(int c = 0; c < SIGMA_SIZE; c++) { int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); last[u] = 0; } } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < SIGMA_SIZE; c++) { int u = ch[r][c]; if(!u) { ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]] ?

f[u] : last[f[u]]; } } } void find_T(char* T) { int n = strlen(T); int j = 0; for(int i = 0; i < n; i++) { int c = idx(T[i]); j = ch[j][c]; if(val[j]) print(j); else if(last[j]) print(last[j]); } } char tmp[105]; char text[1000000+1000]; int main() { //freopen("input.txt", "r", stdin); int T; cin >> T; while(T--) { scanf("%d", &n); Trie trie; ans = 0; for(int i = 0; i < n; i++) { scanf("%s", tmp); trie.insert(tmp); } getFail(); scanf("%s", text); find_T(text); cout << ans << endl; } return 0; }

转载地址：http://efvla.baihongyu.com/

你可能感兴趣的文章