形式化题目

给定小写字母串 $S$（$n = |S|$，$1 \leqslant n \leqslant 1.5 \times 10^4$）和整数 $k$（$1 \leqslant k \leqslant 100$）。统计 $S$ 中形如 $A+B+A$ 的不同子串个数，要求 $|A| \geqslant k$、$|B| \geqslant 1$，即存在一种拆分使子串的前后两段完全相同、中间夹一段非空的 $B$。

计数规则有两层，是本题的关键约束：

• 位置不同算不同子串：起止下标 $(l, r)$ 不同，就是两个答案；
• 位置相同但拆分不同只算一个：同一段 $S[l..r]$ 只要存在一种合法拆分就计 1 次，不管它有多少种拆法。

于是答案就是"存在合法拆分"的下标对 $(l, r)$ 的个数，而不是合法拆分的个数。

样例 1：S = $ `aaaaa`，k = 1$，输出 6。长度不小于 3 的子串全都合格：长度 3 的有 3 个、长度 4 的有 2 个、长度 5 的有 1 个。注意 $S[1..5]$ 既可以拆成 $(a,b) = (1,3)$（a+aaa+a），也可以拆成 $(2,1)$（aa+a+aa），按规则只算 1 个。

样例 2：S = $ `abcabcabc`，k = 2$，输出 8，逐个列出如下（$|A| \geqslant 2$、$|B| \geqslant 1$，两段 $A$ 必须逐字符相同）：

正解

思路

朴素做法：四重枚举。 枚举 $l$、$r$ 和 $A$ 的长度 $a$，再逐位比较两段 $A$ 是否相同。内层比较本身是 $O(n)$，总代价 $O(n^4)$；就算用字符串哈希把比较压成 $O(1)$，也还有 $O(n^3)$，$n = 1.5 \times 10^4$ 时是 $3.4 \times 10^{12}$ 量级，完全不可行。看清瓶颈：所有比较问的其实是同一件事——某两个起点的公共前缀有多长，而同一个 $(l,\ l+i)$ 的答案在不同 $a$、不同 $r$ 下被反复问了很多遍。

第一步：把拆分条件翻译成一个 LCP 条件。 固定子串左端点 $l$，设第二个 $A$ 的起点是 $l+i$（$i \geqslant 1$ 是偏移），$|A| = a$。拆分合法当且仅当三条同时成立：

1. $|A| \geqslant k$，即 $a \geqslant k$；
2. $|B| \geqslant 1$，中间那段长度是 $i - a$，所以 $a \leqslant i - 1$（顺带保证两段 $A$ 不重叠）；
3. 两段 $A$ 逐字符相同，即 $\mathrm{lcp}(l,\ l+i) \geqslant a$，其中 $\mathrm{lcp}(x, y)$ 表示 $S[x..]$ 与 $S[y..]$ 的最长公共前缀。

记 $z_i = \mathrm{lcp}(l,\ l+i)$，三条合起来就是

于是固定 $l$ 和 $i$ 之后，合法的 $a$ 是一整段连续整数；它非空当且仅当 $i \geqslant k+1$（写成判断就是 i > k）且 $z_i \geqslant k$。这一步把"逐个 $a$ 试"换成了"看一个区间是否为空"。

第二步：一个偏移贡献一整段右端点。 右端点 $r = l + i + a - 1$ 随 $a$ 连续移动，所以偏移 $i$ 贡献的右端点（相对 $l$ 的偏移）恰是闭区间

两端的含义分别是"$a$ 取最小值 $k$"和"$a$ 取最大值 $\min(z_i, i-1)$"。

第三步：同一右端点可能被多个偏移产生，求区间并。 对固定 $(l, r)$，拆分中的 $a$ 一旦确定，$i$ 也随之确定（$i = (r-l+1) - a$），所以不同的合法 $a$ 对应不同的 $i$，各自贡献的区间都会包含同一个 $r$——而题目规定同一位置只算一次。因此答案不是区间长度之和，而是这些区间的并。

去重可以线性完成：区间左端 $i + k - 1$ 关于 $i$ 严格递增，按 $i$ 从小到大扫，用 covered 记录已覆盖的最右偏移；遇到新区间 $[b, e]$ 时，若 $e > \texttt{covered}$，就把 $\max(b, \texttt{covered}+1)$ 到 $e$ 这一段从未数过的右端点计入，并把 covered 推到 $e$。每个右端点至多被计入一次。

样例 1 用这套流程逐个左端点走一遍（$k = 1$，"贡献"指相对左端点的右端点偏移）：

关键看 $l = 1$ 的 $i=4$：它的区间 $[4,4]$ 早已被 $i=3$ 的 $[3,4]$ 覆盖，新增为 0。这正是 $S[1..5]$ 的两种拆分（$i=3$ 时 $a=2$，$i=4$ 时 $a=1$）被并集自动合并的时刻。

第四步：用 Z 数组一次求出全部 $z_i$。 对固定 $l$，$z_1, z_2, \dots$ 恰好是段 $S[l..]$ 的 Z 数组：$z[i] = \mathrm{lcp}(S[l..],\ S[l+i..])$。Z 算法维护一个"Z 盒" $[z_l, z_r)$，盒内位置的 $z$ 值可由已算出的值直接截断或复用，只有顶到盒边才继续逐字符比较，整段求完只需 $O(n-l)$ 次比较。这样"两个起点的公共前缀有多长"被问的总次数从"每个拆分问一遍"降到"每个左端点问一遍"。

对每个左端点各做一次 Z 数组 + 一次区间扫描，两步都是 $O(n-l)$，累加即得总复杂度。实现里 $k$ 只用在两个“区间是否非空”的判断上（i > k、zi >= k），并不需要知道 $|A|$ 具体多长。

代码

Python 版：

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#!/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-09-30 13:54
# update_at: 2026-09-30 13:54

import sys


def union_of_ends(seg: bytes, k: int) -> int:
    """以 seg[0] 为子串左端点时，能凑出多少个不同右端点的 A+B+A 子串。

    第二个 A 起点偏移 i 满足 lcp(0,i) >= k 且 i >= k+1（B 非空）时，右端点
    落在连续区间 [i+k-1, i+min(lcp,i-1)-1]；区间左端点随 i 递增，顺序扫一遍
    求区间并，同一右端点（同一子串）就只数一次。
    """
    m = len(seg)
    z = [0] * m          # z[i] = lcp(seg, seg[i:])，经典 Z 数组
    box_l = box_r = 0    # Z 盒：seg[box_l..box_r) 与开头同段
    covered = -1          # 区间并已覆盖到的最右偏移
    ans = 0

    for i in range(1, m):
        zi = 0
        if i < box_r:
            zi = box_r - i
            v = z[i - box_l]
            if v < zi:
                zi = v    # 没顶到盒边：z[i] 已精确，免去逐字符比较
            else:
                # 顶到盒边：从盒边界继续向后逐字符延伸
                while i + zi < m and seg[zi] == seg[i + zi]:
                    zi += 1
        else:
            while i + zi < m and seg[zi] == seg[i + zi]:  # 盒外从头求 lcp
                zi += 1
        if i + zi > box_r:
            box_l, box_r = i, i + zi

        # 偏移 i 贡献的右端点区间：i>k 即 B 至少 1 个字符，zi>=k 即 |A|>=k
        if i > k and zi >= k:
            u = i - 1 if i - 1 < zi else zi   # min(lcp, i-1)：B 不能盖住第二个 A
            b = i + k - 1                      # 区间左端
            e = i + u - 1                      # 区间右端
            if e > covered:
                if b > covered:
                    ans += e - b + 1           # 整段新区间
                else:
                    ans += e - covered         # 只有尾巴是新的
                covered = e
        z[i] = zi                              # 供更后面的 Z 盒取用

    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    text = next(data)
    k = int(next(data))
    print(sum(union_of_ends(text[start:], k) for start in range(len(text))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 02:59
 * update_at: 2026-10-05 02:59
 */
// main.cpp：固定左端点，用 Z 数组一次求出该段全部 lcp，再按偏移递增扫连续右端点区间求并，O(n^2)。
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 15005;

typedef long long ll;

char s[MAXN]; // 题目给定的小写字母串，下标从 1 开始，s[1..n] 有效
ll n;
ll k;
ll z[MAXN]; // z[i] = lcp(s[l..], s[l+i..])，下标是相对当前左端点 l 的偏移，每换一个 l 全部重算

// 统计以 l 为左端点的合法 A+B+A 子串个数（同一子串只算一次）。
// 第二个 A 的起点偏移为 i 时，合法的 |A| 是一段连续整数，于是右端点也落在连续区间里；
// 偏移 i 从小到大递增时区间左端也递增，用 covered 记录已覆盖的最右偏移就能线性去重。
ll count_left(ll l) {
    ll m = n - l + 1;   // 当前段 s[l..n] 的长度
    ll box_l = 0;       // Z 盒：[box_l, box_r) 与 [l, l+box_r-box_l) 逐字符相同
    ll box_r = 0;
    ll covered = -1;    // 区间并已经覆盖到的最右偏移
    ll res = 0;

    for (ll i = 1; i < m; i++) {
        ll zi = 0;
        if (i < box_r) {
            zi = box_r - i;
            ll v = z[i - box_l];
            if (v < zi) {
                zi = v; // 没顶到盒边：z[i] 已精确，不必逐字符比较
            } else {
                while (l + i + zi <= n && s[l + zi] == s[l + i + zi]) zi++; // 顶到盒边，继续向后延伸
            }
        } else {
            while (l + i + zi <= n && s[l + zi] == s[l + i + zi]) zi++; // 盒外从头求 lcp
        }
        if (i + zi > box_r) {
            box_l = i;
            box_r = i + zi;
        }

        // i > k 保证 |B| >= 1，zi >= k 保证 |A| >= k，否则该偏移无合法拆分
        if (i > k && zi >= k) {
            ll upper = zi < i - 1 ? zi : i - 1; // min(lcp, i-1)：两个 A 不能重叠
            ll b = i + k - 1;                   // |A| 取最小 k 时的右端点偏移
            ll e = i + upper - 1;               // |A| 取最大时的右端点偏移
            if (e > covered) {
                if (b > covered) {
                    res += e - b + 1; // 整段区间都是新的
                } else {
                    res += e - covered; // 只有尾部是新的，前面已被别的偏移数过
                }
                covered = e;
            }
        }
        z[i] = zi; // 写在最后，供更后面的位置复用 Z 盒
    }

    return res;
}

void read_input() {
    string text;
    cin >> text >> k;
    n = text.size();
    for (ll i = 1; i <= n; i++) {
        s[i] = text[i - 1];
    }
}

void solve() {
    ll ans = 0;
    for (ll l = 1; l <= n; l++) {
        ans += count_left(l);
    }
    cout << ans << endl;
}

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

    read_input();
    solve();

    return 0;
}

union_of_ends(seg, k) 就是上面四步的合体：内层求 $z_i$（Z 盒写法），紧接着用 covered 做区间并；外层对每个左端点调用一次并累加。注意 z[i] = zi 必须写在循环末尾，供后面位置的 Z 盒复用。

复杂度

• 时间 $O(n^2)$：每个左端点一次 Z 数组 $O(n-l)$、一次区间扫描 $O(n-l)$，全部左端点合计 $\sum_{l=0}^{n-1} 2(n-l) = n(n+1) = O(n^2)$；$n = 1.5 \times 10^4$ 时约 $2.25 \times 10^8$ 次基本操作，字符比较最坏同阶（Z 盒只保证每段线性、不退化到 $O(n^3)$，消不掉这层平方）。本地全量 10 组数据实测最长约 16s，check_sample.py 本地限时放宽到 20s/测例后全部通过；常数主要来自 Python 的逐字符比较。
• 空间 $O(n)$：每个左端点只需一个长度为 $n-l$ 的 Z 数组和 $O(1)$ 个标量，用完即弃。

总结

• 计数规则"同一位置只算一个"决定了正确模型是下标对 $(l,r)$ 的存在性，而不是拆分个数——多个拆分产生的右端点必须取并集。
• 固定左端点后，"是否存在合法拆分"被翻译成 $\mathrm{lcp}(l, l+i)$ 的单个不等式：$i > k$ 且 $z_i \geqslant k$ 时，偏移 $i$ 贡献连续区间 $[i+k-1,\ i+\min(z_i,i-1)-1]$。
• 区间左端随偏移递增，一次带 covered 的扫描即可去重，代价线性；全部 $z_i$ 由 Z 数组线性求出，于是朴素的 $O(n^4)$（哈希后 $O(n^3)$）被压到 $O(n^2)$、空间 $O(n)$。