首页 > 其他 > 详细

UvalLive4670(AC自动机模板)

时间:2019-03-25 22:33:37      阅读:174      评论:0      收藏:0      [点我收藏+]

放上刘汝佳的模板:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <string>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <map>
  7 using namespace std;
  8 
  9 const int maxnod = 150 * 70 + 100;
 10 
 11 int n;
 12 char str[155][75], T[1000005];
 13 map<string, int> mp;
 14 
 15 struct AC_Automata {
 16     int ch[maxnod][26];//Trie树转移
 17     int cnt[155];//每个子串出现了几次
 18     int val[maxnod];//某节点是否为子串结尾以及是哪个串的结尾
 19     int f[maxnod];//失配,转移到别的树枝继续找
 20     int last[maxnod];//找到了后缀相同的其他可行子串
 21     int sz;
 22 
 23     void init() {
 24         sz = 1;
 25         mp.clear();//与ac自动机无关
 26         memset(ch[0], 0, sizeof ch[0]);
 27         memset(cnt, 0, sizeof cnt);
 28     }
 29 
 30     int idx(char c) { return c - a; }
 31 
 32     void insert(char* s, int v) {//Trie树的插入
 33         int u = 0, n =strlen(s);
 34         for (int i = 0; i < n; ++i) {
 35             int c = idx(s[i]);
 36             if (!ch[u][c]) {
 37                 memset(ch[sz], 0, sizeof ch[sz]);
 38                 val[sz] = 0;
 39                 ch[u][c] = sz++;
 40             }
 41             u = ch[u][c];
 42         }
 43         val[u] = v;
 44     }
 45 
 46     void getfail() {
 47         queue<int> Q;
 48         f[0] = 0;
 49         for (int i = 0; i < 26; i++) {
 50             int u = ch[0][i];
 51             if (u) {
 52                 f[u] = last[u] = 0;
 53                 Q.push(u);
 54             }
 55         }
 56         while (!Q.empty()) {
 57             int r = Q.front(); Q.pop();
 58             for (int c = 0; c < 26; c++) {
 59                 int u = ch[r][c];
 60                 if (!u)    continue;
 61                 Q.push(u);
 62                 int v = f[r];
 63                 while (v && !ch[v][c])    v = f[v];//当前这个不行看看别人行不行
 64                 f[u] = ch[v][c];
 65                 last[u] = val[f[u]] ? f[u] : last[f[u]];
 66             }
 67         }
 68     }
 69 
 70     void Success(int j) {
 71         if (j) {
 72             cnt[val[j]]++;
 73             Success(last[j]);
 74         }
 75     }
 76 
 77     void find(char* T) {
 78         int n = strlen(T);
 79         for (int i = 0, j = 0; i < n; ++i) {
 80             int c = idx(T[i]);
 81             while (j && !ch[j][c])    j = f[j];
 82             j = ch[j][c];
 83             if (val[j])    Success(j);
 84             else if (last[j])    Success(last[j]);
 85         }
 86     }
 87 }ac;
 88 
 89 int main() {
 90     while (~scanf("%d", &n) && n) {
 91         ac.init();
 92         for (int i = 1; i <= n; i++) {
 93             scanf("%s", str[i]);
 94             ac.insert(str[i], i);
 95             mp[str[i]] = i;
 96         }
 97         ac.getfail();
 98         scanf("%s", T);
 99         ac.find(T);
100 
101         int ans = -1;
102         for (int i = 1; i <= n; i++) {
103             ans = max(ans, ac.cnt[i]);
104         }
105         printf("%d\n", ans);
106         for (int i = 1; i <= n; i++) {
107             if (ac.cnt[mp[str[i]]] == ans)    puts(str[i]);
108         }
109     }
110     return 0;
111 }

 

UvalLive4670(AC自动机模板)

原文:https://www.cnblogs.com/AlphaWA/p/10597028.html

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