[hdu5164]ac自动机

中文题目：http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=563&pid=1003

首先贴一下bc的题解：

首先我们考虑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的序列）在自动机上跑一遍即可统计出答案。

 事实上，这个题的精华就在于序列变换，将问题转化为多模板匹配问题。而且由于转化后的序列有二维状态，可以用map映射重新为状态分配一个值（类似离散）。另外由于字符集比较大，所以ac自动机里面需要一点小小的修改，原来的二维数组的第二维需用map，另外需要同时记录所有儿子的字符值。原来的模板只需要小改就可以适应这种情况了。详见代码：

#pragma comment(linker, "/STACK:10240000,10240000")

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set>
#include <bitset>
#include <functional>
#include <numeric>
#include <stdexcept>
#include <utility>

using namespace std;

#define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep_up0(a, b) for (int a = 0; a < (b); a++)
#define rep_up1(a, b) for (int a = 1; a <= (b); a++)
#define rep_down0(a, b) for (int a = b - 1; a >= 0; a--)
#define rep_down1(a, b) for (int a = b; a > 0; a--)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pchr(a) putchar(a)
#define pstr(a) printf("%s", a)
#define sstr(a) scanf("%s", a)
#define sint(a) scanf("%d", &a)
#define sint2(a, b) scanf("%d%d", &a, &b)
#define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define pint(a) printf("%d
", a)
#define test_print1(a) cout << "var1 = " << a << endl
#define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl
#define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};
const int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1 };
const int maxn = 3e4 + 7;
const int md = 10007;
const int inf = 1e9 + 7;
const LL inf_L = 1e18 + 7;
const double pi = acos(-1.0);
const double eps = 1e-6;

template<class T>T gcd(T a, T b){return b==0?a:gcd(b,a%b);}
template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;}
template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;}
template<class T>T condition(bool f, T a, T b){return f?a:b;}
template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];}
int make_id(int x, int y, int n) { return x * n + y; }

LL ans;

struct AhoCorasickAutoMata {
    const static int maxn = 250007;
    int cc;
    map<int, int> ch[maxn];
    vector<int> son[maxn];
    int val[maxn], last[maxn], f[maxn];

    void clear() { cc = 0; mem0(val); mem0(ch); mem0(last); mem0(f); rep_up0(i, maxn) { son[i].clear(); ch[i].clear(); } }

    void Insert(int s[], int n) {
        int pos = 0;
        rep_up0(i, n) {
            int id = s[i];
            if(!ch[pos][id]) {
                ch[pos][id] = ++ cc;
                son[pos].push_back(id);
            }
            pos = ch[pos][id];
        }
        val[pos] ++;
    }

    void print(int j) {
        if (j) {
            ans += val[j];
            print(last[j]);
        }
    }

    void find(int T[], int n) {
        int j = 0;
        rep_up0(i, n) {
            int c = T[i];
            while (j && !ch[j][c]) j = f[j];
            j = ch[j][c];
            if (val[j]) print(j);
            else {
                if (last[j]) print(last[j]);
            }
        }
    }

    int getFail() {
        queue<int> q;
        f[0] = 0;
        int SZ = son[0].size();
        rep_up0(i, SZ) {
            int c = son[0][i];
            int u = ch[0][c];
            q.push(u);
        }
        while (!q.empty()) {
            int r = q.front(), SZ = son[r].size(); q.pop();
            rep_up0(i, SZ) {
                int c = son[r][i];
                int u = ch[r][c];
                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]];
            }
        }
    }
};

AhoCorasickAutoMata ac;
map<pii, int> mp;
int pa[100007], pb[100007];
int a[100007], b[300007];

int main() {
    //freopen("in.txt", "r", stdin);
    int T, n, m, tot = 0;
    cin >> T;
    while (T--) {
        ans = 0;
        ac.clear();
        mp.clear();
        cin >> n >> m;
        rep_up0(i, n) {
            sint(a[i]);
        }
        rep_up0(i, n - 1) {
            int g = gcd(a[i], a[i + 1]);
            int ga = a[i] / g, gb = a[i + 1] / g;
            int &x = mp[make_pair(ga, gb)];
            if (!x) x = ++ tot;
            pa[i] = x;
        }

        rep_up0(i, m) {
            int k;
            sint(k);
            rep_up0(j, k) {
                sint(b[j]);
            }
            if (k > n) continue;
            if (k == 1) {
                ans += n;
                continue;
            }
            rep_up0(j, k - 1) {
                int g = gcd(b[j], b[j + 1]);
                int ga = b[j] / g, gb = b[j + 1] / g;
                int &x = mp[make_pair(ga, gb)];
                if (!x) x = ++ tot;
                pb[j] = x;
            }
            ac.Insert(pb, k - 1);
        }
        ac.getFail();
        ac.find(pa, n - 1);
        cout << ans << endl;
    }
    return 0;
}