题目链接

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 - 海胖博客