AC自动机
title: AC自动机
categories:
- ICPC
tags:
- null
abbrlink: 5c28c80e
date: 2023-03-10 00:00:00
AC自动机
- AC 自动机= Trie + KMP
- AC 自动机基于Trie，将KMP 的Border 概念推广到多模式串上。
- AC 自动机是一种离线型数据结构，即不支持增量添加新的字符串。
- AC 自动机常用于将字符串询问类的问题进行离线处理，也经常与各种
DP 结合，或是补全成Trie 图。
广义border
1.推广到两个串：对于两个串S 和T，相等的p 长度的S 的后缀和T 的前缀称为一个border。
2.推广到一个字典：对于串S 和一个字典D，相等的p 长度的S 的后缀，和任意一个字典串T 的前缀称为一个border。
3.失配（Fail）指针： 对于Trie 中的每一个节点（即某个字典串的前缀），它与Trie 中所有串的最大Border 即为失配指针
ac自动机维护的是当前状态的最大后缀满足这个后缀是字典树的前缀
struct AC {
static constexpr int asz = 26;
struct Node { // 表示Trie树的一个节点
int len; // 节点对应的字符串的长度
int fail; // 节点的后缀链接
int mxsuf = 0; // 后缀的恰好匹配一个完整的字典串
bool vis = 0; // 这个状态是不是存在子串是字典串
array<int, asz> next;
// 表示从当前节点到下一个节点的转换，数组大小为字母表大小
Node() : len{0}, fail{0}, next{} {}
};
vector<Node> t;
AC() { init(); }
void init() {
t.assign(2, Node()); // 创建两个节点，分别是根节点和伪根节点
t[0].next.fill(1); // 将根节点的所有next指向伪根节点
t[0].len = -1; // 设置根节点的len为-1
}
int newNode() { // 创建一个新节点，并返回其索引
t.emplace_back(); // 向向量t中添加一个新的Node节点
return t.size() - 1;
}
int add(const string &a, char offset = 'a') { // 向Trie树中添加字符串
int p = 1; // 从伪根节点开始
for (auto c : a) {
int x = c - offset;
if (t[p].next[x] == 0) {
t[p].next[x] = newNode(); // 创建新节点，并更新next数组
t[t[p].next[x]].len = t[p].len + 1;
}
p = t[p].next[x]; // 移动到下一个节点
}
t[p].vis = 1;
t[p].mxsuf = a.size();
return p; // 返回最后一个字符对应的节点索引
}
void work() { // 构建AC自动机的后缀链接
queue<int> q;
q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
t[x].vis |= t[t[x].fail].vis;
t[x].mxsuf = max(t[x].mxsuf, t[t[x].fail].mxsuf);
for (int i = 0; i < asz; i++) {
if (t[x].next[i] == 0) { // 如果当前节点没有对应字符的转移
t[x].next[i] = t[t[x].fail].next[i]; // 设置为后缀链接节点的对应转移
} else {
t[t[x].next[i]].fail = t[t[x].fail].next[i]; // 设置新节点的后缀链接
q.push(t[x].next[i]);
}
}
}
}
int next(int p, int x) { return t[p].next[x]; }
int next(int p, char x, char offset = 'a') { return t[p].next[(x - offset)]; }
int fail(int p) { return t[p].fail; } // 获取节点p的后缀链接
int len(int p) { return t[p].len; }
int mxsuf(int p) { return t[p].mxsuf; } // 获取节点p的匹配的最长后缀，满足他可以与字典串的前缀
bool vis(int p) { return t[p].vis; }
int size() { return t.size(); } // 获取Trie树的节点总数
};
板子：给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。
Sol：将文本串放在AC 自动机上运行，求出每个前缀匹配到AC 自动机的哪
个节点，将该节点的标记值+1。这里标记的是匹配串，下面标记的是模式串
每个字典串的出现次数等于失配树的子树内的标记总量。因此;建出fail树，在失配树上自底向上dfs推标记即可。
void solve() {
AC ac;
cin >> n;
vector<int> id(n + 1);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
id[i] = ac.add(s);
}
ac.work();
string tt;
int p = 1;
cin >> tt;
int tot = ac.size();
vector<int> sz(tot);
m = tt.size();
for (int i = 0; i < m; i++) {
int ch = tt[i] - 'a';
p = ac.next(p, ch);
sz[p] += 1;
deb(p);
}
vector<vector<int>> e(tot);
for (int i = 2; i < tot; i++) {
deb(i, ac.fail(i));
e[ac.fail(i)].push_back(i);
}
auto dfs = [&](auto self, int u) -> void {
for (auto v : e[u]) {
self(self, v);
sz[u] += sz[v];
}
};
dfs(dfs, 1);
for (int i = 1; i <= n; i++) cout << sz[id[i]] << endl;
}
2。https://ac.nowcoder.com/acm/contest/29086/B
- 给出一个有N 个串的字典，然后进行M 次操作：
- 修改操作：向字典中新增一个字典串S。
- 查询操作：查询所有字典串在询问串T 中的出现次数，同一个字典
串重复出现算多次。
1 ≤ N, M ≤ 100, 000, 输入字符串总长度不超过3000, 000。
Sol：AC自动机无法在线处理，所以考虑离线询问。先无视修改操作，只考虑查询操作：可以建出AC 自动机。
然后将查询串在AC 自动机上运行，匹配到AC 自动机的一个节点时，将该节点到根的路径上终止标记个数计入答案。
由于AC 自动机是离线型数据结构，即不能支持快速增删字典串，因此
考虑到修改操作需要先离线，动态维护终止标记，使用dfs 序+ 树状数
组快速维护每个点到根路径上的终止标记个数。这里说一下怎么维护的？我们需要查询的是查询串在AC自动机上走的时候faill链上有多少标记？但是这样直接做不好做，我们考虑每个终止标记只会贡献它的fail子树，所以标记字典串完成区间加，而查询是单点查。正好符合dfs序+树状数组
debug:由于在跑ac自动机的时候字母和数字映射内部没写，外部也没有处理。现在板子加了offset，减小出错概率。不过也要惊醒这个点
void solve() { int n, m; AC ac; cin >> n >> m; vector<int> pos; for (int i = 1; i <= n; i++) { string s; cin >> s; pos.push_back(ac.add(s)); } vector<pii> q(m); vector<int> id(m); for (int i = 0; i < m; i++) { int x; string y; cin >> x >> y; q[i].fs = x, q[i].sec = y; if (x == 1) id[i] = ac.add(y); } ac.work(); int tot = ac.size() - 1; vector<vector<int>> e(tot + 1); for (int i = 2; i <= tot; i++) e[ac.fail(i)].push_back(i); int idx = 0; vector<int> l(tot + 1), r(tot + 1); auto dfs = [&](auto self, int u) -> void { l[u] = ++idx; for (auto v : e[u]) { self(self, v); } r[u] = idx; }; dfs(dfs, 1); Fwk<int> fw(tot + 2); for (auto x : pos) { deb(l[x], r[x]); fw.add(l[x], 1); fw.add(r[x] + 1, -1); } for (int i = 0; i < m; i++) { auto [x, y] = q[i]; if (x == 1) { fw.add(l[id[i]], 1); fw.add(r[id[i]] + 1, -1); } else { int p = 1; int res = 0; for (auto it : y) { p = ac.next(p, it-'a'), res += fw.sum(l[p]); } cout << res << endl; } } }$\sum_{v是u的祖先}(i-len(v)+1) \times (len(询问串)-i+1) $
3.给出一个字典，至多包含300, 000 个字典串，且字典串总长度不超过
300, 000。
再给出一个文本串T(|T| ≤ 300, 000)，问最少使用多少个字典串可以拼
接出T。同一个字典串使用多次算多次。
拼接时允许重叠，只需要保证重叠部分匹配即可，例如T = abcd，可以
使用字典串S = cdxx 拼接成T′ = abcdxx。
Sol:首先比较容易想到使用DP：f[i] 表示拼接出T[1, i] 的操作次数.
转移时，设某字典串Si 等于T[1, i] 的后缀，会导致如下转移：
$f[i] = min(f[i − 1], f[i − 2], · · · , f[i − |Si|]]) + 1$。因此只需要寻找满足长度最长的字典串恰好能和当前后缀完美匹配，我们可以选择只让后缀的子后缀匹配，所以是区间转移，用线段树辅助进行DP 转移。
复杂度O(300000 · (26 + log n))。
struct Info {
int mx = inf;
};
Info operator+(const Info &a, const Info &b) {
return {min(a.mx, b.mx)};
}
void solve() {
cin >> n;
AC ac;
string s;
cin >> s;
for (int i = 1; i <= n; i++) {
string t;
cin >> t;
ac.add(t);
}
ac.work();
s = " " + s;
int len = s.size() - 1;
vector<int> dp(len + 1, inf);
SegmentTree<Info> seg(len + 1);
int p = 1;
dp[0] = 0;
seg.modify(0, {dp[0]});
deb(inf);
for (int i = 1; i <= len; i++) {
p = ac.next(p, s[i] - 'a');
int tmp = ac.mxsuf(p);
deb(tmp);
if (tmp == 0)
continue;
int l = max(0, i - tmp);
dp[i] = min(dp[i], seg.rangeQuery(l, i).mx + 1);
seg.modify(i, {dp[i]});
}
if (dp[len] == inf)
cout << -1 << endl;
else
cout << dp[len] << endl;
}
4.给出一个字典，至多包含60 个字典串，且字典串总长度不超过100。
求所有长度为M(≤ 100) 的串中（共$26^M$ 个），有多少个串至少包含一
个字典串
Sol:考虑容斥，答案= $26^M$- 完全不包含字典串的串个数。
包含与不包含本质上都是字符串匹配问题，因此本题为字符串多模式匹
配，很容易想到利用AC 自动机。
设$f[len][u] $表示长度为len 的字符串，当前匹配到了AC 自动机的u 节
点的方案数。
转移时枚举下一个字符，然后找到匹配的AC 自动机节点v(这一步的复
杂度为O(depth))，如果v 是一个终止节点，则是一个不合法的转移。
复杂度O(M · 100 · 100 · 26) =$ 2.7 · 10^7$
加强长度为M=10000
- Trie 图
用上题的做法复杂度高达$2.7 · 10^9 $不能通过。因此需要进行优化：
可以比较容易的观察到，可以预处理出$trans[u][ch]$ =AC 自动机节点u，后
面添加字符ch 后会转移到哪个节点。如此可以省掉跳Fail 链的复杂度。
求$trans[u][ch] $时，讨论：
- 如果u 节点有ch 后继边，则$trans[u][ch] = nxt[u][ch]$。
- 否则$，trans[u][ch] = trans[Fail[u]][ch]$。
因此trans 数组也需要使用bfs 来求，可以和AC 自动机的构造放在一起进行
- 否则$，trans[u][ch] = trans[Fail[u]][ch]$。
实现：由于为了卡做法，本题取模卡常，需要用取模类
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
template <class T> constexpr T power(T a, i64 n) {
T res{1};
for (; n > 0; n /= 2, a *= a) {
if (n % 2 == 1) {
res *= a;
}
}
return res;
}
template <i64 P> constexpr i64 mul(i64 a, i64 b) {
i64 res = a * b - i64(1.0L * a * b / P - 0.5L) * P;
return res % P;
}
template <i64 P> struct ModInt {
static i64 M;
constexpr static void setMod(i64 m) { ModInt::M = m; }
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return M;
}
}
i64 x;
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
} else if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr ModInt() : x{} {}
constexpr ModInt(i64 x) : x{norm(x % getMod())} {}
constexpr i64 val() const { return x; }
explicit constexpr operator i64() const { return x; }
constexpr ModInt operator-() const { return ModInt(getMod() - x); }
constexpr ModInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr ModInt &operator+=(const ModInt &rhs) {
x = norm(x + rhs.x);
return *this;
}
constexpr ModInt &operator-=(const ModInt &rhs) {
x = norm(x - rhs.x);
return *this;
}
constexpr ModInt &operator*=(const ModInt &rhs) {
if (getMod() < (1LL << 31)) {
x = 1LL * x * rhs.x % P;
} else {
x = mul<getMod()>(x, rhs.x);
}
return *this;
}
constexpr ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) { return lhs += rhs; }
friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) { return lhs -= rhs; }
friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) { return lhs *= rhs; }
friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) { return lhs /= rhs; }
friend constexpr bool operator<(const ModInt &lhs, const ModInt &rhs) { return lhs.val() < rhs.val(); }
friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val() == rhs.val(); }
friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.val() != rhs.val(); }
friend istream &operator>>(istream &is, ModInt &rhs) {
i64 x;
is >> x;
rhs = x;
return is;
}
friend ostream &operator<<(ostream &os, const ModInt &rhs) { return os << rhs.val(); }
};
template <> i64 ModInt<0>::M = 1000000007;
template <i64 V, i64 P> constexpr ModInt<P> CInv = ModInt<P>(V).inv();
constexpr int P = 10007;
using Z = ModInt<P>;
考虑对于一个字典串的终止节点，它的fail树子树都会被染成非法节点，所以dfs去完成染色是容易的。但为了减小常数，我们可以在ac自动机的构建过程去维护vis表示是不是包含
int add(const string &a) { // 向Trie树中添加字符串
int p = 1; // 从伪根节点开始
for (auto c : a) {
int x = c - 'A';
if (t[p].next[x] == 0) {
t[p].next[x] = newNode(); // 创建新节点，并更新next数组
t[t[p].next[x]].len = t[p].len + 1;
}
p = t[p].next[x]; // 移动到下一个节点
}
t[p].vis = 1;
t[p].mxsuf = a.size();
return p; // 返回最后一个字符对应的节点索引
}
void work() { // 构建AC自动机的后缀链接
queue<int> q;
q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
t[x].mxsuf = max(t[x].mxsuf, t[t[x].fail].mxsuf);
t[x].vis |= t[t[x].fail].vis;
for (int i = 0; i < asz; i++) {
if (t[x].next[i] == 0) { // 如果当前节点没有对应字符的转移
t[x].next[i] = t[t[x].fail].next[i]; // 设置为后缀链接节点的对应转移
} else {
t[t[x].next[i]].fail = t[t[x].fail].next[i]; // 设置新节点的后缀链接
// t[t[x].next[i]].vis |= t[t[t[x].fail].next[i]].vis;
// t[t[x].next[i]].ended |= t[t[t[x].link].next[i]].ended;
q.push(t[x].next[i]);
}
}
}
}
考虑每层的长度的转移是互相不牵连的，用滚动数组dp.本题在ac自动机上转移主要关注的是vis标记的躲避，与具体最长border无关。这里的ac自动机节点看作一个状态。
void solve() {
AC ac;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
ac.add(s);
}
ac.work();
int tot = ac.size() - 1;
vector<Z> dp(tot + 1);
dp[1] = 1;
for (int i = 1; i <= m; i++) {
vector<Z> ndp(tot + 1);
for (int p = 1; p <= tot; p++) {
for (int x = 0; x < 26; x++) {
int v = ac.next(p, x);
if (ac.vis(v))
continue;
ndp[v] += dp[p];
}
}
dp = move(ndp);
// dp = move(ndp); 的核心作用是通过移动语义避免拷贝，
// 从而提高性能。ndp 在执行这句代码后可能会变为空或处于未定义状态，因此后续不要再直接使用 ndp。
}
Z ans = 0;
for (int i = 1; i <= tot; i++) {
ans += dp[i];
}
cout << power(Z(26), m) - ans << "\n";
}
6.给出N ≤ 2, 000 个01 串，它们每一个表示一段病毒序列，病毒代码总
长度不超过30, 000。
求是否存在无限长度的01 串，不包含任意病毒序列作为子串。
Sol:本题本质是问：Trie 图上（去掉所有终止节点）是否存在无限长度的路
径，充要条件为：有环。
因此本题需要先构造AC 自动机，然后补全成为Trie 图，找到所有包含病毒序列的节点。使用拓扑排序或者dfs判定是否有环。
- 注意，这个环必须是root 节点可达的。
复杂度O(30, 000 · 2)。
void solve() {
int n;cin >> n;
AC ac;
for (int i = 1; i <= n; i++) {string s;cin >> s;ac.add(s);}
ac.work();
int tot = ac.size() - 1;
vector<vector<int>> e(tot + 1);
for (int i = 1; i <= tot; i++) {
for (int j = 0; j < 2; j++) {
int v = ac.next(i, j);
if (ac.vis(i))continue;
e[i].push_back(v);
}
}
vector<int> st(tot + 1);
auto dfs = [&](auto self, int u) {
st[u] = 1;
for (auto v : e[u]) {
if (st[v] == 2)continue;
if (st[v] == 1)return true;
if (self(self, v))return true;
}
st[u] = 2;
return false;
};
bool flag = dfs(dfs, 1);
if (flag)cout << "TAK";
else cout << "NIE";
}
8.CF547E给出N 个字符串，设f(S, T) 表示T 在S 中的出现次数。
给出Q 次询问：给定L, R, K，求$\sum_{i=L}^{i\leq R} f(S_{i}, S_{K})$
本题做法很多，其中一种做法是《AC 自动机Fail 树Dfs 序上建可持久
化线段树》。
- 先建出AC 自动机，在回答询问的时候先找到$S_{K}$所在的节点u，那么
完整包含字符串$S_{K}$ 的状态节点一定位于u 的Fail 树子树内。
即问题等价于询问u 的Fail 树子树内，$S_{L}$, $S_{L+1}$, · · · , $S_{R}$ 的前缀节点个
数有多少。
考虑子树求和，比较容易转化为Dfs 序的区间求和，对字典串的区间询问，容易转化成持久化数据结构。即Dfs 序上建可持久化线段树。
具体来说对每个字符串都会在前缀结点上标记加1，我们去结点的dfs序对应位置上加1，这每一次修改都需要动态开点我们都可以认为这是一个的新版本，但我们需要的是每个字符串之间的版本的权值数量差距。
AC ac;
void solve() {
int n, m;
cin >> n >> m;
vector<int> pos(n + 1);
vector<string> s(n + 1);
for (int i = 1; i <= n; i++) {
cin >> s[i];
pos[i] = ac.add(s[i]);
}
ac.work();
int tot = ac.size() - 1;
vector<vector<int>> e(tot + 1);
for (int i = 2; i <= tot; i++) {
e[ac.fail(i)].push_back(i);
}
deb(e);
vector<int> in(tot + 1), out(tot + 1);
int idx = 0;
auto dfs = [&](auto self, int u) -> void {
deb(u);
in[u] = ++idx;
for (auto v : e[u]) {
self(self, v);
}
out[u] = idx;
};
dfs(dfs, 1);
Segment<Info> seg(tot + 5);
vector<int> ver{0};
for (int i = 1; i <= n; i++) {
int prev = ver.back();
for (int p = 1; auto c : s[i]) {
p = ac.next(p, c);
prev = seg.modify(prev, in[p], {1}); // 每次都有当前字符串长度的修改
// 一个版本需要开len*log(len)的新点
}
ver.push_back(prev); // 以一个字符串为一个版本
}
for (int i = 1; i <= m; i++) {
int l, r, k;
cin >> l >> r >> k;
Info res = seg.rangeQuery(ver[l-1], ver[r], in[pos[k]], out[pos[k]] + 1);
cout << res.x << endl;
}
}
- 另一个版本的主席树https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71321487&returnHomeType=1&uid=291321052
- 重要基础结论：$s_{k}$的出现次数就是fail树子树内的(字典树前缀结尾节点)出现次数总和
考虑使用轻量级的dfs序配合树状数组。离线询问，将询问差分，只要求k在前缀L-1中出现次数和求k在前缀R中出现次数。
将询问挂在这两个位置，顺序扫描字符串。每次将当前字典串上的前缀节点加1，然后处理当前节点挂的多个询问，注意加个op表示是加还是减，对于查询就是对当前k的fail树子树内求和
code：
10.https://www.luogu.com.cn/problem/P2414[NOI2011] 阿狸的打字机
题意：给出一颗字典树，多次查询第x个字符串在第y个字符串出现了多少次？
Sol:首先题目以特定的当时生成字典树，仔细思考发现我们不能把所有构成的字符串存下来，也不能每次从头开始走路，而是要动态维护一个p指针和字典树节点的父亲来完成建树。
struct Node { // 表示Trie树的一个节点
int len; // 节点对应的字符串的长度
int fail; // 节点的后缀链接
int mxsuf = 0; // 后缀的恰好匹配一个完整的字典串
bool vis = 0; // 这个状态是不是存在子串是字典串
array<int, asz> next;
int fa = 1;//字典树的父亲
// 表示从当前节点到下一个节点的转换，数组大小为字母表大小
Node() : len{0}, fail{0}, next{} {}
};
int add(int p, char c, char offset = 'a') { // 向Trie树中添加字符串
int x = c - offset;
if (t[p].next[x] == 0) {
t[p].next[x] = newNode(); // 创建新节点，并更新next数组
t[t[p].next[x]].len = t[p].len + 1;
t[t[p].next[x]].fa = p;
}
p = t[p].next[x]; // 移动到下一个节点
return p; // 返回最后一个字符对应的节点索引
}
考虑问题本身：x在y中出现了多少次，就是x的fail树子树内有多少个y的字典树前缀结点。我们需要子树求和，考虑dfs序加树状数组完成这个操作。
- 把询问挂到y上，dfs字典树动态维护标记，进去的时候加1，出来的时候减1，这样能保证每次只查单串的贡献，每次退出递归的时候判一下这个点上有没有询问。
细节：要记录pos数组表示第x个字符串的结尾节点编号。字典树dfs由于建的是trie图所以我们需要判一下长度来完成正确的字典树遍历。
AC ac;
void solve() {
string s;cin >> s;string tmp;
vector<int> pos; pos.push_back(-1);
int n = 0,p = 1;
for (auto x : s) {
if (x == 'B') {
p = ac.fa(p);
} else if (x == 'P') {
n++;
pos.push_back(p);
} else
p = ac.add(p, x);
}
//------------------------------------//
ac.work();
int tot = ac.size() - 1;
vector<bool> vis(tot + 1);
for (int i = 1; i <= n; i++) vis[pos[i]] = true;
//-----------------------------------------
int m;
cin >> m;
vector<vector<pii>> q(tot + 1);
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
q[pos[y]].push_back({pos[x], i});
}
vector<int> ans(m + 1);
//-----------------------------------------------
vector<vector<int>> e(tot + 1);
for (int i = 2; i <= tot; i++) e[ac.fail(i)].push_back(i);
vector<int> l(tot + 1), r(tot + 1);
int idx = 0;
auto dfs = [&](auto self, int u) -> void {
l[u] = ++idx;
for (auto v : e[u]) {
self(self, v);
}
r[u] = idx;
};
dfs(dfs, 1);
//-------------------------------------------------
Fwk<int> fw(tot + 1);
auto cal = [&](auto self, int u) -> void {
fw.add(l[u], 1);
for (int i = 0; i < 26; i++) {
int v = ac.next(u, i);
if (ac.len(v) == ac.len(u) + 1) {
self(self, v);
}
}
if (vis[u]) {
for (auto [x, id] : q[u]) {
ans[id] = fw.rangeSum(l[x] - 1, r[x]);
}
}
fw.add(l[u], -1);
};
cal(cal, 1);
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！