[HDU][ACM]5164 Matching on Array
海胖子 - 2015/01/25题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5164
题目大意
对于两个序列A和B,如果A中有一个连续子序列在乘以某个缩放系数之后和B一样的话,那么B在A中出现。
Alice有一个大小为n的正整数序列{a1,a2,…,an}。Bob也有一些正整数序列。Alice想要知道对于Bob的每个序列,他们在Alice的序列中出现的总次数是多少。
题解
首先我们考虑m = 1的情况。
给定两个数组A = {a1,a2,…,an}和B = {b1,b2,…,bk},问B在A中出现了几次。令ci = ai+1/ai (1≤i<n),同样令di = bi+1/bi (1≤i<k),那么上述问题可以转化为ci和di的模式匹配问题,这个正确性显然,也没有什么好证明的。于是对于m = 1的情况用个KMP即可搞定。
现在考虑m > 1的情况,我们考虑用AC自动机来做。
考虑到字符集并不是普通的数字,而是一个分数,我们不放搞个分数类,然后用map存转移边。用m个模式串(Bob的序列)建好自动机之后,把文本串(Alice的序列)在自动机上跑一遍即可统计出答案。
代码
// // main.cpp // 5164 // // Created by 林海鸿 on 15/1/25. // Copyright (c) 2015年 林海鸿. All rights reserved. // #include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <queue> #include <map> #include <algorithm> using namespace std; const int N = 1e5, K = 3e5; struct trie { int count; map<double, trie*> next; trie *fail; trie() { next.clear(); count = 0; fail = NULL; } }; int a[N + 5], b[K + 5]; double ta[N + 5], tb[K + 5]; int Next[K + 5]; queue<trie*> Q; void getNext(double *B, int m) { Next[1] = 0; for (int i = 2, j = 0; i <= m; ++i) { while (j > 0 && B[j + 1] != B[j]) j = Next[j]; if (B[j + 1] == B[i]) ++j; Next[i] = j; } return; } int KMP(double *A, int n, double *B, int m) { int res = 0; for (int i = 1, j = 0; i <= n; ++i) { while (j > 0 && B[j + 1] != A[i]) j = Next[j]; if (B[j + 1] == A[i]) ++j; if (j == m) { ++res; j = Next[j]; } } return res; } void insert(trie *root, double *B, int m) { trie *cur = root; for (int i = 1; i <= m; ++i) { if (cur->next.find(B[i]) == cur->next.end()) cur->next[B[i]] = new trie(); cur = cur->next[B[i]]; } ++cur->count; return; } void build(trie *root) { while (!Q.empty()) Q.pop(); Q.push(root); while (!Q.empty()) { trie *cur = Q.front(); Q.pop(); for (map<double, trie*>::iterator i = cur->next.begin(); i != cur->next.end(); ++i) { if (cur == root) cur->next[i->first]->fail = root; else { trie *tmp = cur->fail; while (tmp) { if (tmp->next[i->first]) { cur->next[i->first]->fail = tmp->next[i->first]; break; } tmp = tmp->fail; } if (tmp == NULL) cur->next[i->first]->fail = root; } Q.push(cur->next[i->first]); } } return; } int query(trie *root, double *A, int n) { int res = 0; trie *cur = root; for (int i = 1; i <= n; ++i) { while (cur->next[A[i]] == NULL && cur != root) cur = cur->fail; cur = cur->next[A[i]]; if (cur == NULL) cur = root; trie *tmp = cur; while (tmp != root && tmp) { res += tmp->count; tmp = tmp->fail; } } return res; } int main() { freopen("5164.in", "r", stdin); freopen("5164.out", "w", stdout); int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i < n; ++i) ta[i] = (double)a[i + 1]/(double)a[i]; if (m == 1) { int k; scanf("%d", &k); for (int i = 1; i <= k; ++i) scanf("%d", &b[i]); if (k == 1) { printf("%d\n", n); continue; } for (int i = 1; i < k; ++i) tb[i] = (double)b[i + 1]/(double)b[i]; getNext(tb, k - 1); int ans = KMP(ta, n - 1, tb, k - 1); printf("%d\n", ans); } else { long long ans = 0; trie *root = new trie(); while (m--) { int k; scanf("%d", &k); for (int i = 1; i <= k; ++i) scanf("%d", &b[i]); if (k == 1) { ans += n; continue; } for (int i = 1; i < k; ++i) tb[i] = (double)b[i + 1]/(double)b[i]; insert(root, tb, k - 1); } build(root); ans += query(root, ta, n - 1); printf("%lld\n", ans); } } fclose(stdin); fclose(stdout); return 0; }
转载保留版权:http://haipz.com/blog/i/6410 - 海胖博客