最佳文章

GitHub跳转原题关系图 Canvas 关系图返回列表

在 AC 自动机上建立 max-plus 转移矩阵，快速幂求超长文章的最大匹配次数。

OJ: shumeng

题目 ID: CSP201509E

难度:提高+/省选-

标签:AC 自动机矩阵快速幂动态规划

日期: 2026-07-31 16:21

形式化题目

给定 $n$ 个单词和一个目标长度 $m$ ，构造一个恰好 $m$ 个字符的文章，使得这 $n$ 个单词在文章中的总出现次数最大。出现可以重叠、可以互相包含，每次出现都单独计数。

思路

先看一个只适用于短文章的枚举基准：枚举每个位置选择哪个字母，写满长度后统计总出现次数。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
// brute.cpp：枚举所有小文章，并在追加字符时统计以当前位置结尾的单词。
#include <bits/stdc++.h>
using namespace std;

int n, length;
vector<string> words; // 重要单词列表
vector<char> letters; // 出现过的字母种类
string article;       // 当前构造中的文章
long long answer;

// 枚举第 position 个位置选择哪个字母；文章写满 length 个字母后更新答案。
void dfs(int position, long long score) {
    if (position == length) {
        answer = max(answer, score);
        return;
    }
    for (int i = 0; i < (int)letters.size(); i++) {
        article += letters[i];
        // 只统计“以当前位置结尾”的单词出现次数，避免重复计数。
        long long added = 0;
        for (int j = 0; j < n; j++) {
            int word_length = words[j].size();
            if ((int)article.size() >= word_length &&
                article.substr(article.size() - word_length) == words[j]) added++;
        }
        dfs(position + 1, score + added);
        article.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> length;
    words.resize(n);
    int used[26] = {};
    for (int i = 0; i < n; i++) {
        cin >> words[i];
        for (int j = 0; j < (int)words[i].size(); j++) used[words[i][j] - 'a'] = 1;
    }
    for (int i = 0; i < 26; i++) if (used[i]) letters.push_back('a' + i);
    dfs(0, 0);
    cout << answer << '\n';
    return 0;
}

brute.cpp 用选择序列递归枚举整篇文章，每个位置尝试所有出现过的字母，时间复杂度为指数级，只适合小数据，但最忠实于题意。

DP 状态：AC 自动机

逐字符构造文章时，影响后续匹配的只有“当前文章后缀能匹配到的最长前缀”——这正是 AC 自动机的状态。用 $dp[i]$ 表示写到某一步、落在状态 $i$ 时能得到的最大重要度。

把每个单词插入 Trie，用 BFS 建好失配指针后，把子串的分数累加到父节点，这样走到某个状态时，score 就是“以当前位置结尾的所有重要单词数”，包含与重叠出现都被累计。

矩阵快速幂

长度 $m$ 高达 $10^{15}$ ，逐字符 DP 不可行，但状态转移是固定的。令矩阵 $T[u][v]$ 表示“从状态 $u$ 追加一个字符到状态 $v$ 能增加的最大重要度”，在 max-plus 代数下（加法变取 max、乘法变加法） $T^k$ 就表示走 $k$ 步的最优加分：

初始向量只有根状态为 $0$ ，其余为负无穷；
用二进制快速幂把转移矩阵自乘、按需乘到答案向量上， $m$ 步的最优值就是对所有状态取 max。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXS = 105;
const long long NEG = -(1LL << 60); // 不可达状态，max 运算下的“负无穷”

// AC 自动机节点：next[c] 是字符 c 的转移，fail 是失配指针，
// score 是“以该状态结尾时能新增的匹配次数”。
struct Node {
    int next[26];
    int fail;
    int score;
};

// max-plus 意义下的转移矩阵：value[i][j] 表示从状态 i 走一步到 j 能得到的最大加分。
struct Matrix {
    long long value[MAXS][MAXS];
};

Node trie[MAXS]; // AC 自动机节点数组，下标 0 是根节点
int node_count = 1;

// 在 max-plus 代数下做矩阵乘法：C[i][j] = max_k (A[i][k] + B[k][j])。
Matrix multiply(const Matrix &left, const Matrix &right, int states) {
    Matrix result;
    for (int i = 0; i < states; i++) {
        for (int j = 0; j < states; j++) result.value[i][j] = NEG;
    }
    for (int i = 0; i < states; i++) {
        for (int k = 0; k < states; k++) {
            if (left.value[i][k] == NEG) continue;
            for (int j = 0; j < states; j++) {
                if (right.value[k][j] == NEG) continue;
                result.value[i][j] = max(result.value[i][j],
                                         left.value[i][k] + right.value[k][j]);
            }
        }
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long length;
    cin >> n >> length;

    // 把每个单词插入 Trie，单词末尾的 score 加 1。
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        int current = 0;
        for (int j = 0; j < (int)word.size(); j++) {
            int c = word[j] - 'a';
            if (trie[current].next[c] == 0) trie[current].next[c] = node_count++;
            current = trie[current].next[c];
        }
        trie[current].score++;
    }

    // BFS 构建失配指针，并把子串的分数累加到父节点：让包含关系与重叠出现都被计数。
    queue<int> q;
    for (int c = 0; c < 26; c++) {
        int child = trie[0].next[c];
        if (child != 0) q.push(child);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        trie[u].score += trie[trie[u].fail].score;
        for (int c = 0; c < 26; c++) {
            int v = trie[u].next[c];
            if (v != 0) {
                trie[v].fail = trie[trie[u].fail].next[c];
                q.push(v);
            } else {
                trie[u].next[c] = trie[trie[u].fail].next[c];
            }
        }
    }

    // 构造一步转移矩阵：从状态 i 沿字符 c 走到 v，获得 score[v] 分。
    Matrix transition;
    for (int i = 0; i < node_count; i++) {
        for (int j = 0; j < node_count; j++) transition.value[i][j] = NEG;
        for (int c = 0; c < 26; c++) {
            int v = trie[i].next[c];
            transition.value[i][v] = max(transition.value[i][v], (long long)trie[v].score);
        }
    }

    // best[i] 表示写出的前缀落在状态 i 时能得到的最大重要度，起点只能是根。
    long long best[MAXS] = {};
    for (int i = 1; i < node_count; i++) best[i] = NEG;
    // 二进制快速幂：把 transition 当作“走一步”，对 length 步做 max-plus 幂。
    while (length > 0) {
        if (length & 1) {
            long long next_best[MAXS];
            for (int j = 0; j < node_count; j++) next_best[j] = NEG;
            for (int i = 0; i < node_count; i++) {
                if (best[i] == NEG) continue;
                for (int j = 0; j < node_count; j++) {
                    next_best[j] = max(next_best[j], best[i] + transition.value[i][j]);
                }
            }
            for (int i = 0; i < node_count; i++) best[i] = next_best[i];
        }
        transition = multiply(transition, transition, node_count);
        length >>= 1;
    }
    long long answer = 0;
    for (int i = 0; i < node_count; i++) answer = max(answer, best[i]);
    cout << answer << '\n';
    return 0;
}

复杂度

设自动机状态数为 $S \leqslant 100$ 。

时间：建自动机 $O(S \cdot 26)$ ，每次矩阵乘法 $O(S^3)$ ，共 $\log m$ 次，总时间 $O(S^3\log m)$ 。
空间：存储矩阵与 Trie， $O(S^2 + S \cdot 26)$ 。

总结

超长长度使逐字符 DP 不可行，但转移规则固定。把普通加法换成“取最大值和加奖励”，构造 max-plus 意义下的矩阵，快速幂就能跳过任意多次相同转移。AC 自动机负责把“后缀匹配到哪个前缀”压缩成有限个状态，是这类“无限长度、有限状态”问题的标准组合。

时间限制： 1.0 秒

空间限制： 256 MB

问题描述

小明最近在研究一门新的语言，叫做 Q 语言。Q 语言单词和文章都可以用且仅用只含有小写英文字母的字符串表示，任何由这些字母组成的字符串也都是一篇合法的 Q 语言文章。

在 Q 语言的所有单词中，小明选出了他认为最重要的 $n$ 个。使用这些单词，小明可以评价一篇 Q 语言文章的“重要度”。

文章“重要度”的定义为：在该文章中，所有重要的 Q 语言单词出现次数的总和。其中多次出现的单词，不论是否发生包含、重叠等情况，每次出现均计算在内。

例如，假设 $n = 2$ ，小明选出的单词是 gvagv 和 agva。在文章 gvagvagvagv 中，gvagv 出现了 $3$ 次，agva 出现了 $2$ 次，因此这篇文章的重要度为 $3+2=5$ 。

现在，小明想知道，一篇由 $m$ 个字母组成的 Q 语言文章，重要度最高能达到多少。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n, m$ ，表示小明选出的单词个数和最终文章包含的字母个数。

接下来 $n$ 行，每行包含一个仅由英文小写字母构成的字符串，表示小明选出的这 $n$ 个单词。

输出格式

输出到标准输出。

输出一行一个整数，表示由 $m$ 个字母组成的 Q 语言文章中，重要度最高的文章的重要度。

input1

1
2
3
43 15
agva
agvagva
gvagva

output1

样例 1 解释

$15$ 个字母组成的重要度最高的文章为 gvagvagvagvagva。

在这篇文章中，agva 出现 $4$ 次，agvagva 出现 $3$ 次，gvagva 出现 $4$ 次，共计 $4+3+4=11$ 次。

评测用例规模与约定

在评测时将使用 $10$ 个评测用例对你的程序进行评测。

设 $s$ 为构成 $n$ 个重要单词字母的总个数，例如在样例中， $s=4+7+6=17$ ； $a$ 为构成 $n$ 个重要单词字母的种类数，例如在样例中，共有 $3$ 中字母 a, g, v，因此 $a=3$ 。

对于所有数据，保证 $1\le n\le 30,~1 \le m \le 10^{15},~1 \le s \le 100$ ，每个单词至少包含 $1$ 个字母，保证单词中仅出现英文小写字母，输入中不含多余字符，不会出现重复的单词。

测试点编号	特殊性质
$1\sim 2$	$2 \le n \le 3,~1500 \le m \le 2000,~s = 40$
$3\sim 4$	$m = 20,~2 \le a \le 3$
$5\sim 7$	$2000 \le m \le 100000$
$8$	$n=2$
$9\sim 10$	无

最佳文章

目录

形式化题目

思路

DP 状态：AC 自动机

矩阵快速幂

代码

复杂度

总结