首页 > 代码库 > HDU 5164Matching on Array(AC自动机)

HDU 5164Matching on Array(AC自动机)

2024-11-25 08:35:02   204人阅读

这是BC上的一道题，当时比赛没有做，回头看看题解，说是AC自动机，想着没有写过AC自动机，于是便试着抄抄白书的模板，硬是搞了我数个小时2000ms时限1800过了= = ！

这里就直接贴上BC的结题报告（#27）：http://bestcoder.hdu.edu.cn/solutions.php

1003 Matching on Array首先我们考虑m=1的情况。给定两个数组A={a1,a2,…,an}和B={b1,b2,…,bk}，问B在A中出现了几次。令ci=ai+1ai,1≤i<n，同样令di=bi+1bi,1≤i<k，那么上述问题可以转化为ci和di的模式匹配问题，这个正确性显然，也没有什么好证明的。于是对于m=1的情况只有用个kmp即可搞定。现在考虑m>1的情况，我们考虑用ac自动机来做。考虑到字符集并不是普通的数字，而是一个分数，我们不放搞个分数类，然后用map存转移边。用m个模式串（Bob的序列）建好自动机之后，把文本串（Alice的序列）在自动机上跑一遍即可统计出答案。

 

然后是我的代码：

技术分享

  1 #include <map>  2 #include <set>  3 #include <stack>  4 #include <queue>  5 #include <cmath>  6 #include <ctime>  7 #include <vector>  8 #include <cstdio>  9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 1e9 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 #define rep(i, a, b) for(int i = a; i <= b; i ++) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    } 31  32 typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 110000; 35 const int MAXM = 1000006; 36 const double eps = 1e-10; 37 const LL MOD = 1000000007; 38  39 int T, n, m, s, k, x, y; 40 //val[p]用来存放以节点p结尾的字典树中共有多少个模式串(包含在失配链中的模式串) 41 //f是失配函数， last用于记录失配链上的上一个结点(不是节点， 具体见白书, 这里last数组可以删除) 42 int val[MAXM], f[MAXM], last[MAXM]; 43 LL ans; 44  45 struct Node {//自定义分数类型， 并重载几个必要的运算符 46     int up, down;//分子及分母 47     Node(){} 48     Node(int _up, int _down) { 49         int g = GCD(_up, _down); 50         up = _up / g; 51         down = _down / g; 52     } 53     bool operator == (const Node& A) const { 54         return up == A.up && down == A.down; 55     } 56     bool operator != (const Node& A) const { 57         return up != A.up || down != A.down; 58     } 59     bool operator <  (const Node& A) const { 60         if(up != A.up) return up < A.up; 61         return down < A.down; 62     } 63 }; 64  65 map<int, map<Node, int> >ch;//字典树链 66 vector<Node>e[MAXM];//邻接表存边 67 Node fa[MAXN], chi[MAXN];//记录查找串(father)以及模式串(child) 68  69 void init()//初始化 70 { 71     s = 1;  ans = 0; //s是字典树的大小 72     ch.clear(); e[0].clear(); 73     mem0(val); mem0(f); mem0(last); 74 } 75  76 void input(int n, Node* a)//输入 77 { 78     scanf("%d", &x); 79     for(int i = 1; i < n; i ++) { 80         scanf("%d", &y); 81         a[i - 1] = Node(x, y); 82         x = y; 83     } 84 } 85  86 void addEdge()//想字典树上插入一条链，目前val[p]存放的是到达结点p的相同的链的条数 87 { 88     int p = 0; 89     for(int i = 0; i < k - 1; i ++) { 90         Node u = chi[i]; 91         if(ch[p][u] == 0) {//第二维是Node类型 92             e[p].push_back(u);//记录边 93             val[s] = 0; 94             e[s].clear();//扩展出一条新边之前，把边清空 95             ch[p][u] = s++; 96         } 97         p = ch[p][u]; 98     } 99     val[p] ++;//说明之前有这样一条链,条数++100 }101 102 void getFail()//拿到字典树上的失配函数，与白书几乎一致，只是改成了邻接链表存边103 {104     queue<int>q;105     for(int i = 0; i < e[0].size(); i ++) {106         int u = ch[0][e[0][i]];107         f[u] = last[u] = 0;108         q.push(u);109     }110     while(!q.empty()) {111         int r = q.front(); q.pop();112         for(int i = 0; i < e[r].size(); i ++) {113             Node c = e[r][i];114             int u = ch[r][c];115             if(!u) {116                 ch[r][c] = ch[f[r]][c];117                 continue;118             }119             q.push(u);120             int v = f[r];121             while(v && !ch[v][c]) v = f[v];122             f[u] = ch[v][c];123             last[u] = val[f[u]] ? f[u] : last[f[u]];124             val[u] += val[last[u]];//加上了一句，表示以u结尾的链的条数125         }126     }127 }128 129 void getNext()130 {131     f[0] = f[1] = 0;132     for(int i = 1; i < k - 1; i ++) {133         int j = f[i];134         while(j && chi[i] != chi[j]) j = f[j];135         f[i + 1] = chi[i] == chi[j] ? j + 1 : 0;136     }137 }138 139 LL KMP()140 {141     if(k == 1) return ans;142     getNext();143     int j = 0;144     for(int i = 0; i < n - 1; i ++) {145         while(j && chi[j]!=fa[i]) j = f[j];146         if(chi[j] == fa[i]) j ++;147         if(j == k - 1) ans ++;148     }149     return ans;150 }151 152 //void calc(int j)153 //{154 //    if(j) {155 //        ans += val[j];156 //        calc(last[j]);157 //    }158 //}159 160 LL ACT()//AC自动机查找过程161 {162     getFail();163     int j = 0;164     for(int i = 0; i < n - 1; i ++) {165         Node c = fa[i];166         while(j && !ch[j][c]) j = f[j];//失配链往回匹配167         j = ch[j][c];168         ans += val[j];//加上条数169         //if(last[j]) calc(last[j]);170     }171     return ans;172 }173 174 int main()175 {176     //FOPENIN("in.txt");177     //FOPENOUT("out.txt");178     while(~scanf("%d", &T)) while(T--) {179         scanf("%d %d", &n, &m);180         init();181         input(n, fa);//输入查找串182         for(int i = 1; i <= m; i ++) {183             scanf("%d", &k);184             input(k, chi);185             if(k > 1) addEdge();186             else ans += n;//由于k=1时只有一个数直接加上n即可187         }188         cout<< (m == 1 ? KMP() : ACT()) << endl;//输出答案189     }190     return 0;191 }

 

HDU 5164Matching on Array(AC自动机)


联系
我们