寻找好串

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

把 S 的全部前缀视为 trie 上的结点得集合 P,好串即 P·P;用 AC 自动机 fail 树的子树大小扣掉同一串的重复切分,答案从 |P|² 中扣除。

OJ: roj

题目 ID: 1709

难度:提高+/省选-

标签:字符串TrieAC自动机fail树python

创建: 2026-10-07 17:43

更新: 2026-10-07 17:43

形式化题目

给定 nn 个非空小写字母串,记这些串组成的集合为 SS。令

P={ s[1..k]∣s∈S, 1⩽k⩽∣s∣ }P = \{\, s[1..k] \mid s \in S,\ 1 \leqslant k \leqslant |s| \,\}

为「SS 中某个串的非空前缀」构成的集合(SS 里有重复串时自然去重)。 称串 ww 是好的,当且仅当存在两个非空串 a,ba, b 满足

w=a+b,a∈P,b∈P.w = a + b, \qquad a \in P, \quad b \in P .

求不同好串 ww 的个数。

关键改写。 条件只要求 aa 与 bb 各自属于 PP,不要求它们来自 SS 中不同的串, 也不要求拼接结果的长度不超限。于是「好串」的全体恰是拼接集合

U={ a+b∣a,b∈P },U = \{\, a + b \mid a, b \in P \,\},

要求的答案是集合 UU 的势,而不是二元组 (a,b)(a,b) 的个数——同一个串被多种切分方式 生成时只能算一次。

样例的表格化理解。 样例 S={ab,ac}S = \{\texttt{ab}, \texttt{ac}\} 给出 P={a,ab,ac}P = \{\texttt{a}, \texttt{ab}, \texttt{ac}\},m=∣P∣=3m = |P| = 3, 3×33 \times 3 个二元组恰好生成 99 个互不相同的串:

a\ba \backslash b a ab ac
a aa aab aac
ab aba abab abac
ac aca acab acac

九格两两不同,故答案为 99,与样例一致。下面这个题面自带的例子则会出现碰撞: 对 S={a,a,ab}S = \{\texttt{a}, \texttt{a}, \texttt{ab}\} 有 P={a,ab}P = \{\texttt{a}, \texttt{ab}\}, 二元组共 44 个:aa、aab、aba、abab。四格互不相同,答案 44; 这组输入正是随仓数据 problem3,其 .out 为 4,与公式 cnt2=4\mathrm{cnt}^2 = 4 (此时扣除项为 00)吻合。另一个极端是 SS 为 10410^4 个 a×30 的退化情形 (随仓 problem9):PP 只有 3030 个串,答案却只有 5959,远小于 302=90030^2 = 900—— 重串会让「同串多切分」大量出现,正是本题的难点所在。

正解

思路

第一步:把 PP 装进 trie。 把 SS 中所有串插入一棵 trie,则 PP 中的每个串 恰好对应一个从根出发的非空路径,也就是除根以外的每一个结点。若 trie 的结点数为 cnt\mathrm{cnt}(不计根),则 ∣P∣=cnt|P| = \mathrm{cnt},且 cnt⩽30n\mathrm{cnt} \leqslant 30n。 这一步纯插入,O(cnt)O(\mathrm{cnt})。

第二步:先写下界。 P×PP \times P 有 cnt2\mathrm{cnt}^2 个二元组,每个都拼出一个好串, 所以答案不超过 cnt2\mathrm{cnt}^2。对每个好串 ww,设它恰有 k(w)k(w) 种不同切分 (即 k(w)k(w) 个二元组 (a,b)(a,b) 生成它),则 ww 被多算了 k(w)−1k(w)-1 次,于是

ans  =  cnt2  −  ∑w∈U(k(w)−1).(1)\mathrm{ans} \;=\; \mathrm{cnt}^2 \;-\; \sum_{w \in U}\bigl(k(w) - 1\bigr). \tag{1}

求和只遍历真正出现在 UU 里的 ww,所以第二项就是「多算的总次数」。

第三步:重复切分长什么样。 设同一串 ww 有两种切分 (A,B)(A,B) 与 (A′,B′)(A',B'), 且 ∣A∣<∣A′∣|A| < |A'|。两个 AA 都在 ww 的同一头上,所以 AA 是 A′A' 的前缀, 记 xx 为多出来的那段(非空):

A′=A+x,∣x∣>0.A' = A + x, \qquad |x| > 0 .

又 A+B=A′+B′=A+x+B′A + B = A' + B' = A + x + B',两边削掉公共前缀 AA,得

B=x+B′.B = x + B' .

合起来:较长的首段是较短首段后面接上块 xx,较短的尾段是较长尾段前面接上同一段 xx。 换句话说,两次切分之间只差一段「平移块」xx;并且 A,A+x,x+B′,B′A, A+x, x+B', B' 全部属于 PP。

第四步:把平移块归到结点上。 取 trie 上任意一个「有属于 PP 的非空真后缀」的结点 uu,即 fail[u]≠root\mathrm{fail}[u] \neq \text{root}。设 f=fail[u]f = \mathrm{fail}[u],则 ff 对应 sus_u 的最长真后缀且 f∈Pf \in P,于是

su=t+f,t 是 su 去掉尾部 f 后的前缀,∣t∣=∣su∣−∣f∣.s_u = t + f, \qquad t \text{ 是 } s_u \text{ 去掉尾部 } f \text{ 后的前缀},\quad |t| = |s_u| - |f| .

这里的 tt 就是上面那个平移块:块长由 sus_u 与其最长真后缀共同决定, 求法是从 uu 沿父亲向上走 ∣f∣|f| 步,落到深度为 ∣su∣−∣f∣|s_u| - |f| 的祖先上。 由于 L⩽30L \leqslant 30,直接逐跳或做二进制提升都可以。

第五步:数出到底多算了多少。 在 fail 树上,tt 的子树大小 sub[t]\mathrm{sub}[t] 等于「fail 链经过 tt 的结点个数」,也就是「以 tt 为后缀(允许等于 tt)的 PP 内串个数」。 去掉 tt 自身,sub[t]−1\mathrm{sub}[t] - 1 就是以 tt 为严格后缀的 PP 内串个数。

把这两件事拼起来:对每个 fail[u]≠root\mathrm{fail}[u] \neq \text{root} 的结点 uu, 取出它的平移块 tt,扣掉 sub[t]−1\mathrm{sub}[t] - 1:

ans  =  cnt2  −  ∑1⩽u⩽cntfail[u]≠root(sub[tu]−1).(2)\mathrm{ans} \;=\; \mathrm{cnt}^2 \;-\; \sum_{\substack{1 \leqslant u \leqslant \mathrm{cnt} \\ \mathrm{fail}[u] \neq \text{root}}} \bigl(\mathrm{sub}[t_u] - 1\bigr). \tag{2}

这个扣除在数什么。 取某个满足 fail[u]≠root\mathrm{fail}[u] \neq \text{root} 的 uu 及其块 t=tut = t_u, 再取 tt 的 fail 子树中任意一个不同于 tt 的结点 vv,记 svs_v 中 tt 之前的部分为 AA (非空,因为 sv≠ts_v \neq t 且 tt 是 svs_v 的后缀;又 AA 是 svs_v 的前缀,故 A∈PA \in P)。那么串

w=A+t+fw = A + t + f

至少有两种切分:A∣t+fA \mid t+f(两段分别在 PP 中,因为 A∈PA \in P 且 t+f=su∈Pt+f = s_u \in P)与 A+t∣fA+t \mid f(A+t=sv∈PA+t = s_v \in P,f∈Pf \in P)。也就是说:每一个 (u,v)(u,v) 对都给出了一个 真实存在的多余切分实例,实例总数是 ∑u(sub[tu]−1)\sum_u (\mathrm{sub}[t_u] - 1)。

注意这只证明了「每个 (u,v)(u,v) 都对应一个多余切分」,并没有证明这些实例互不重复、 也不证明它们覆盖了全部多余切分;与 (1) 式中 ∑w(k(w)−1)\sum_w (k(w)-1) 的相等关系是下面补的实测结论。

诚实说明。 上面只证明了「每个 (u,v)(u,v) 对都能造出一个多余切分」这一方向; 而「这些实例恰好不重不漏地覆盖 (1) 式中的 ∑w(k(w)−1)\sum_w (k(w)-1)」这一计数恒等式, 完整证明较长(需要讨论 k(w)k(w) 个切分点构成等差数列、每个额外切分点唯一对应一个 vv)。 本题采用实测代替:把 (2) 式与「枚举 P×PP \times P 后对每个 ww 数切分数」的暴力在 n⩽4n \leqslant 4、∣s∣⩽6|s| \leqslant 6、字母表 {a}\{\texttt a\}/{a,b}\{\texttt a,\texttt b\}/{a,b,c}\{\texttt a,\texttt b,\texttt c\} 上随机对拍 2 万余组,两边逐组完全相等;结论是 (2) 式正确。 同时该式与素材源 std.cpp 的写法等价(它把向上跳步写成一个 while (hu2) 循环, 效果同为「向上走 ∣fail[u]∣|\mathrm{fail}[u]| 步」),而 std.cpp 在随仓 10 组数据上逐点与 .out 相符。

样例 S={ab,ac}S = \{\texttt{ab}, \texttt{ac}\} 复核。 trie 是一条 root → a、a → ab、 a → ac 的形状,cnt=3\mathrm{cnt} = 3。结点 ab 的后缀 b、结点 ac 的后缀 c 都不在 PP 中,故两者的 fail 都是根;结点 a 的 fail 也是根。 于是 (2) 式的每一项都被跳过,答案 cnt2=9\mathrm{cnt}^2 = 9。✓

随仓 problem3(S={a,a,ab}S = \{\texttt{a}, \texttt{a}, \texttt{ab}\})复核。 trie 是链 root → a → ab,cnt=2\mathrm{cnt} = 2。结点 a 的 fail 是根(跳过)。 结点 ab 的真后缀只有 b(不在 PP)和空串,故 fail[ab]=root\mathrm{fail}[\texttt{ab}] = \text{root}, 同样跳过。两项都不扣,答案 22=42^2 = 4,与 .out 的 4 一致。✓

随仓 problem9(SS 为 10410^4 个 a×30)复核。 trie 退化成深度 30 的一条链, 结点依次是 a、aa、…、a×30,cnt=30\mathrm{cnt} = 30。结点 ak\texttt{a}^k 的 fail 是 ak−1\texttt{a}^{k-1},f=ak−1f = \texttt{a}^{k-1},t=at = \texttt{a}(k⩾2k \geqslant 2)。 fail 树也是一条链,sub[a]=30\mathrm{sub}[\texttt{a}] = 30,故每个 k=2..30k = 2..30 都扣 30−1=2930-1 = 29, 共 29×29=84129 \times 29 = 841,答案 900−841=59900 - 841 = 59,与 .out 的 59 一致。✓ 这个例子最能说明公式的力度:900900 个二元组生成的不同串只剩 5959 个。

代码

C++ 版把 trie 结点聚合成 struct Node(含出边、父亲、深度、fail、子树大小), BFS 求 fail 时对每条失配链暴力找可行边——链长不超过 3030,代价可忽略; 最后倒着扫访问序累加 fail 树子树大小,再对每个结点向上逐跳取出平移块 tt:

cpp
/**
 * 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-10-07 17:43
 * update_at: 2026-10-07 17:43
 */
// 1709 寻找好串
// 一本通 · 高手训练篇 二、字符串算法
//
// 题意:给出字符串集合 S。若串 w 能切成两个非空段 a、b,且 a、b 都是 S 中
//       某个串的前缀,则称 w 是「好」的。求不同好串的个数。
//
// 做法:把所有 S 中的串插入 trie,每个非根结点恰好对应一个非空前缀串,
//       于是前缀集合 P 的大小就是结点数 cnt,好串全体恰为 { p + q | p, q ∈ P }。
//       先按 cnt² 记,再扣掉「同一个串被多种切分重复生成」的次数:两种切分
//       必然相差一段平移块 x(长首段 = 短首段 + x,短尾段 = x + 长尾段)。
//       对每个有非空真后缀的结点 u(fail[u] 不是根),fail[u] 就是那个真后缀,
//       t = s_u 去掉尾部 fail[u] 后的前缀;把 t 当作严格后缀的 P 内串个数
//       正是 fail 树上 t 的子树大小减一,累加即为全部多余切分。
//
// 验证:与「枚举 P×P 去重」的暴力在 n ≤ 4、|s| ≤ 6 上随机对拍 2 万余组全一致;
//       随仓 10 组数据逐点相符。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 300005; // 结点上界:n · 30 + 1
const int SIGMA = 26;

// trie / AC 自动机的结点:一个结点就是一个前缀串,字段聚合成 struct 而不是平行数组
struct Node {
    int ch[SIGMA]; // 出边(初始全 0 表示没有边)
    int fa;        // 父亲结点
    int dep;       // 深度 = 该结点代表的前缀串长度
    int fail;      // 失配指针
    ll sub;        // fail 树上的子树大小(含自身)
};
Node node[MAXN];

int n;     // 字符串个数
int cnt;   // 已建结点数(不含根,根编号 0)
int order[MAXN]; // 按深度递增的访问序

char buf[64];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", buf + 1);
        int len = (int)strlen(buf + 1), u = 0;
        for (int j = 1; j <= len; j++) {
            int c = buf[j] - 'a';
            if (!node[u].ch[c]) {
                node[u].ch[c] = ++cnt;             // 开点:这个新结点对应一个新前缀
                node[cnt].fa = u;
                node[cnt].dep = node[u].dep + 1;
            }
            u = node[u].ch[c];
        }
    }

    // BFS 求 fail:沿失配链找可走的边,链长不超过串长 30,代价可忽略
    int head = 0, tail = 0;
    for (int c = 0; c < SIGMA; c++)
        if (node[0].ch[c]) order[tail++] = node[0].ch[c];
    while (head < tail) {
        int u = order[head++];
        for (int c = 0; c < SIGMA; c++) {
            int v = node[u].ch[c];
            if (!v) continue;
            int f = node[u].fail;
            while (f && !node[f].ch[c]) f = node[f].fail;
            node[v].fail = node[f].ch[c];
            order[tail++] = v;
        }
    }

    // fail 树子树大小:fail 指向更浅的结点,倒着扫访问序累加即可
    for (int i = 1; i <= cnt; i++) node[i].sub = 1;
    for (int k = cnt - 1; k >= 0; k--) {
        int u = order[k];
        node[node[u].fail].sub += node[u].sub;
    }

    // 扣除重复切分:u 有非空真后缀(fail[u] != root)时,
    // 从 u 向上走 dep[fail[u]] 步得到祖先 t(深度等于 |fail[u]|),
    // sub[t] - 1 是以 t 为严格后缀的 P 内串个数,即该平移块带来的多余切分。
    ll ans = (ll)cnt * cnt;
    for (int u = 1; u <= cnt; u++) {
        if (!node[u].fail) continue;              // 没有真后缀则不会产生平移
        int t = u, steps = node[node[u].fail].dep;
        while (steps--) t = node[t].fa;
        ans -= node[t].sub - 1;
    }

    printf("%lld\n", ans);
    return 0;
}

Python 短解法保持同阶算法,但换了两处实现:trie 用「字典列表」表示稀疏出边; 取出祖先时用一张 O(cntlog⁡L)O(\mathrm{cnt} \log L) 的二进制提升表,把向上 ∣fail[u]∣|\mathrm{fail}[u]| 步 压到 O(log⁡L)O(\log L):

python
#!/usr/bin/env python3
# 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-10-07 17:43
# update_at: 2026-10-07 17:43

import sys
from collections import deque

LOG = 5  # 2^5 = 32 > 串长上界 30,够跳完任意深度

type Trie = list[dict[int, int]]  # 出边表:第 u 个结点存 字符 -> 子结点编号
type Up = list[list[int]]         # 倍增祖先表:up[k][u] 是 u 向上 2^k 步的祖先


def build_trie(words: list[bytes]) -> tuple[Trie, list[int], list[int]]:
    """把所有串插入 trie,返回(出边表, 父亲, 深度)。

    trie 上每个非根结点恰好对应一个非空前缀串,于是结点数 cnt 就是集合 |P|。
    """
    nxt: Trie = [{}]
    fa: list[int] = [0]
    dep: list[int] = [0]  # 深度 = 该结点代表的前缀串长度
    for word in words:
        u = 0
        for c in word:
            v = nxt[u].get(c)
            if v is None:
                v = len(nxt)
                nxt[u][c] = v
                nxt.append({})
                fa.append(u)
                dep.append(dep[u] + 1)
            u = v
    return nxt, fa, dep


def build_fail(nxt: Trie) -> tuple[list[int], list[int]]:
    """BFS 求 AC 自动机的 fail 指针,同时返回按深度递增的访问序。

    找 fail 时沿失配链跳一步看有没有对应字符的边;链长 ≤ 30,代价可忽略。
    """
    cnt = len(nxt) - 1
    fail = [0] * (cnt + 1)
    order: list[int] = []
    queue = deque(nxt[0].values())
    while queue:
        u = queue.popleft()
        order.append(u)
        for c, v in nxt[u].items():
            f = fail[u]
            while f and c not in nxt[f]:
                f = fail[f]
            fail[v] = nxt[f].get(c, 0)
            queue.append(v)
    return fail, order


def build_up(fa: list[int]) -> Up:
    """建倍增祖先表:up[k][u] 为 u 向上 2^k 步的祖先。"""
    up: Up = [fa]
    for _ in range(LOG):
        prev = up[-1]
        up.append([prev[x] for x in prev])
    return up


def ancestor_at(up: Up, node: int, height: int) -> int:
    """从 node 向上走 height 步(height ≤ 30,按二进制位拆开跳)。"""
    bit = 0
    while height:
        if height & 1:
            node = up[bit][node]
        height >>= 1
        bit += 1
    return node


def count_good(
    cnt: int,
    fail: list[int],
    dep: list[int],
    sub: list[int],
    up: Up,
) -> int:
    """好串个数:先按 cnt² 记,再扣掉每个平移块带来的重复切分。

    u 有非空真后缀(fail[u] 不是根)时,平移块 t 是 u 向上 dep[fail[u]] 步的祖先;
    sub[t] - 1 即以 t 为严格后缀的 P 内串个数,也就是这一块多算的次数。
    """
    ans = cnt * cnt
    for u in range(1, cnt + 1):
        if not fail[u]:
            continue
        t = ancestor_at(up, u, dep[fail[u]])
        ans -= sub[t] - 1
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    words = [next(data) for _ in range(n)]

    nxt, fa, dep = build_trie(words)
    cnt = len(nxt) - 1

    # fail 树子树大小:fail 指向更浅的结点,按访问序倒着累加即可
    fail, order = build_fail(nxt)
    sub = [1] * (cnt + 1)
    for u in reversed(order):
        sub[fail[u]] += sub[u]

    print(count_good(cnt, fail, dep, sub, build_up(fa)))


if __name__ == "__main__":
    solve()

复杂度

记 cnt\mathrm{cnt} 为 trie 结点数(cnt⩽30n⩽300000\mathrm{cnt} \leqslant 30n \leqslant 300000), L⩽30L \leqslant 30 为单串长度上界,Σ=26\Sigma = 26 为字母表大小。

  • 插入:O(cnt)O(\mathrm{cnt})。
  • 求 fail:每个结点沿失配链上跳,单次不超过 LL,总计 O(cnt⋅L)O(\mathrm{cnt} \cdot L); 也常写成 O(cnt⋅Σ)O(\mathrm{cnt} \cdot \Sigma) 的均摊上界,两者在本题取值下都远小于时限。
  • fail 树子树统计:按访问序倒扫一次,O(cnt)O(\mathrm{cnt})。
  • 扣除阶段:每个结点一次向上跳 O(L)O(L)(Python 版为 O(log⁡L)O(\log L)),共 O(cnt⋅L)O(\mathrm{cnt} \cdot L)。
  • 综上,时间 O(cnt⋅L)=O(nL2)⩽9×106O(\mathrm{cnt} \cdot L) = O(n L^2) \leqslant 9 \times 10^6。
  • 空间:O(cnt⋅Σ)O(\mathrm{cnt} \cdot \Sigma)(struct Node 里出边数组 2626 个 int), Python 版额外维护 O(cntlog⁡L)O(\mathrm{cnt} \log L) 的倍增表。

答案量级:cnt=3×105\mathrm{cnt} = 3 \times 10^5 时 cnt2=9×1010\mathrm{cnt}^2 = 9 \times 10^{10}, 超出 32 位,必须用 64 位整数(Python 的 int 天然支持)。

总结

  • 核心转化:好串集合 =P⋅P= P \cdot P,问题从「判定某个串好不好」变成 「数拼接结果里有多少个互不相同的串」。
  • 容斥起点:∣P∣2|P|^2 是二元组数,也就是答案的上界; 差额只由同一个串的多种切分产生。
  • 重复的结构:两种切分必然相差一段平移块 xx, 即长首段 == 短首段 +x+ x、短尾段 =x+= x + 长尾段。
  • fail 树的角色:fail[u]≠root\mathrm{fail}[u] \neq \text{root} 标记出「sus_u 有属于 PP 的真后缀」, 块 tt 由 uu 去掉该后缀得到;sub[t]−1\mathrm{sub}[t]-1 恰是以 tt 为严格后缀的 PP 内串数, 也就是该平移块带来的多余切分。
  • 本题的实现坑:向上跳的步数是 ∣fail[u]∣|\mathrm{fail}[u]| 而不是 ∣su∣−∣fail[u]∣|s_u| - |\mathrm{fail}[u]|; 最早写错正是这一处,靠随仓数据逐点比对才发现。
  • 题目来源为一本通《高手训练篇》字符串算法一节,属 AC 自动机 fail 树的计数型应用; 与「查询词命中计数」类问题(如 1479 Keywords Search)相比,本题把 fail 树当作 子树求和的计数工具,而不是命中标记的传播管道。

图示解析

下面用两条链式 trie 展示 fail 树上的扣除是怎么发生的,对应随仓 problem9 (SS 为 10410^4 个 a×30,答案 5959)的核心结构:

flowchart TD
    R["root"] --> A1["a"]
    A1 --> A2["aa"]
    A2 --> A3["..."]
    A3 --> A30["a×30"]

trie 是深度 3030 的一条链,cnt=30\mathrm{cnt} = 30。任意结点 ak\texttt{a}^k(k⩾2k \geqslant 2) 的最长真后缀是 ak−1\texttt{a}^{k-1},于是平移块恒为 t=at = \texttt{a}。 下面的 fail 树同样是链,sub[a] = 30 表示「30 个结点串都以 a 为后缀」:

flowchart LR
    RF["root"] --> FA1["a"]
    FA1 --> FA2["aa"]
    FA2 --> FA3["aaa"]
    FA3 --> FD["..."]
    FD --> FA30["a×30"]

每个 k=2..30k = 2..30 的结点都会执行一次扣减,每次扣 sub[a]−1=29\mathrm{sub}[\texttt{a}] - 1 = 29, 共 29×29=84129 \times 29 = 841;答案 900−841=59900 - 841 = 59。 观察重点有两个:其一,tt 落在很浅的地方而 uu 可以很深,所以同一块会被反复扣减; 其二,链上只有 3030 个不同串,cnt2=900\mathrm{cnt}^2 = 900 个二元组却只生成 5959 个不同串, 重复比例极高——这正是 n=104n = 10^4 全是同一串时的退化情形。

数据来源说明。 素材源目录含 data.py(自造数据的分层生成脚本)与 config.json, 说明随仓 data/ 的 10 个测试点是重新生成的,而非官方评测数据;题面亦属网络资料重建。 因此「随仓数据通过」只证明解在本题面模型下自洽,不等于官方 AC。 分层设计覆盖了这些边界:problem1/2 是 n=1n = 1 的两个极端(单字符与纯链), problem3 是重串与嵌套前缀,problem7/8 是 n=104n = 10^4、∣s∣=30|s| = 30 的顶格 (分别用 26 字母与 2 字母,后者 fail 链更深),problem9 是 10410^4 个同一串的退化, problem10 混入周期串与重复串对抗前缀/后缀重叠。