「BZOJ 2580」Video Game - AC 自动机

给出 个串 ，求一个长度为 的串 ，使 匹配 （可重叠）的次数最多。

链接

BZOJ 2580

题解

设 表示已生成的 个字符组成的串在 AC 自动机上匹配的状态为第 个节点，之后再生成 个字符后的总最大匹配数量。

枚举下一个字符，如果是单词节点则对应答案为当前匹配数量 目标节点单词数量（自身单词和由后缀链接能转移到的单词），否则为当前匹配数量。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

const int MAXN = 15;
const int MAXM = 20;
const int MAXK = 1000;
const int CHARSET_SIZE = 26;
const int BASE_CHAR = 'A';

struct Trie {
    struct Node {
        Node *c[CHARSET_SIZE], *fail, *next;
        bool isWord;
        int wordCnt, id;

        Node(const bool isWord = false) : fail(NULL), next(NULL), isWord(isWord) {
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }
    } *root;

    Trie() : root(NULL) {}

    void insert(const char *begin, const char *end) {
        Node **v = &root;
        for (const char *p = begin; p != end; p++) {
            if (!*v) *v = new Node;
            v = &(*v)->c[*p];
        }
        if (!*v) *v = new Node(true);
        else (*v)->isWord = true;
    }

    void build(std::vector<Node *> &vec) {
        std::queue<Node *> q;
        q.push(root);
        root->fail = root, root->next = NULL;
        while (!q.empty()) {
            Node *v = q.front();
            v->id = vec.size();
#ifdef DBG
            printf("wordCnt(%d) = %d\n", v->id, v->wordCnt);
#endif
            vec.push_back(v);
            q.pop();

            for (int i = 0; i < CHARSET_SIZE; i++) {
                Node *&c = v->c[i];
                if (!c) {
                    c = v->fail->c[i] ? v->fail->c[i] : root;
                    continue;
                }
                Node *u = v->fail;
                while (u != root && !u->c[i]) u = u->fail;
                c->fail = v != root && u->c[i] ? u->c[i] : root;
                c->next = c->fail->isWord ? c->fail : c->fail->next;
                c->wordCnt = c->isWord + (c->next ? c->next->wordCnt : 0);
                q.push(c);
            }
        }
    }
} t;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    while (n--) {
        static char s[MAXN + 1];
        scanf("%s", s);
        const int len = strlen(s);
        for (int i = 0; i < len; i++) s[i] -= BASE_CHAR;
        t.insert(s, s + len);
    }

    std::vector<Trie::Node *> vec;
    t.build(vec);

    static int f[MAXN * MAXM + 1][MAXK + 1];
#ifdef DBG
    static char g[MAXN * MAXM + 1][MAXK + 1];
#endif
    // for (size_t i = 0; i < vec.size(); i++) f[i][0] = vec[i]->wordCnt;

    for (int i = 1; i <= k; i++) {
        for (size_t j = 0; j < vec.size(); j++) {
            for (int k = 0; k < CHARSET_SIZE; k++) {
                int t = f[vec[j]->c[k]->id][i - 1] + vec[j]->c[k]->wordCnt;
                if (t >= f[j][i]) {
                    f[j][i] = t;
#ifdef DBG
                    g[j][i] = k;
#endif
                }
            }
#ifdef DBG
            printf("f(%lu, %d) = %d\n", j, i, f[j][i]);
#endif
        }
    }

#ifdef DBG
    int last = 0;
    for (int i = k; i >= 1; i--) {
        putchar(g[last][i] + 'A');
        last = vec[last]->c[g[last][i]]->id;
    }
    putchar('\n');

    last = 0;
    for (int i = k; i >= 1; i--) {
        printf("%d%c", last, i == 1 ? '\n' : ' ');
        last = vec[last]->c[g[last][i]]->id;
    }
#endif

    printf("%d\n", f[0][k]);

    return 0;
}