形式化题目

记 $conn(s,n)$ 为字符串 $s$ 首尾相接 $n$ 次。称 $a$ 能由 $b$ 生成，当且仅当 $a$ 是 $b$ 的子序列（从 $b$ 中删除若干字符、保持顺序可得 $a$）。

给定 $s_1,n_1,s_2,n_2$，求最大的整数 $m$，使得

其中 $|s_1|,|s_2|\leqslant 100$，$n_1,n_2\leqslant 10^6$，多组数据读到文件结束。

正解

思路

第一步：把 $m$ 还原成"能放几份 $s_2$"

因为 $conn(conn(s_2,n_2),m)=conn(s_2,\,m\cdot n_2)$，所以"$conn(s_2,n_2)$ 重复 $m$ 次是 $T$ 的子序列"和"$s_2$ 重复 $m\cdot n_2$ 次是 $T$ 的子序列"是同一件事。记 $T=conn(s_1,n_1)$，记

$c=\text{s_2$ 作为子序列在 $T$ 中最多能不重叠地出现的次数}$$

那么答案就是

于是问题只剩一件事：数出 $c$。

第二步：朴素扫描，以及它为什么不够快

最直接的做法是逐字符贪心：展开 $T$，用指针 $j$ 指向 $s_2$ 中下一个要匹配的字符，从左到右扫 $T$；遇到 s1[pos] == s2[j] 就匹配并让 $j$ 前进，$j$ 走完一整份 $s_2$ 时计数加一、$j$ 归零。

以样例第一组（$s_1=\texttt{acb}$，$n_1=4$；$s_2=\texttt{ab}$，$n_2=2$）为例：

1
2
3
4
5
6T   :  a  c  b  a  c  b  a  c  b  a  c  b
下标:  0  1  2  3  4  5  6  7  8  9 10 11
第1份:  a  .  b                          → 跨过 1 份 s1，落点回到份首
第2份:           a  .  b                 → 跨过 1 份 s1
第3份:                    a  .  b        → 跨过 1 份 s1
第4份:                             a  .  b → 跨过 1 份 s1

$c=4$，答案 $m=\lfloor 4/2\rfloor=2$。

其余四组样例各自检验一个侧面：

"能匹配就立刻匹配"是安全的：匹配得越早，留给 $s_2$ 剩余部分的空间只会越大，不存在"这次先跳过、以后更划算"的情况。

但这个扫描是 $O(n_1|s_1|)=O(10^8)$ 次比较，而且 $T$ 本身就长达 $10^8$，根本不能真的展开。注意轨迹里每份 $s_2$ 的匹配过程完全一样——都从份内偏移 $0$ 出发、都在份内偏移 $0$ 结束。这就是可以压缩的地方。

第三步：把"匹配一份 $s_2$"压成一次状态转移

一份 $s_2$ 怎么匹配，只取决于"从哪一份 $s_1$ 的哪个偏移 $p$ 出发"。于是定义：

1match_once(p) = ( 匹配一份 s2 跨过的完整 s1 份数 blocks, 匹配结束时的份内偏移 q )

状态只有 $|s_1|\leqslant 100$ 种，全部预处理出来即可。样例第一组（$s_1=\texttt{acb}$）的三条转移：

match_once 也不需要展开 $T$：扫到一份 $s_1$ 的末尾就把位置模 $|s_1|$ 归零、份数加一，等价于把 $T$ 沿 $|s_1|$ 的边界切块后继续扫。只要 $s_2$ 的字符都在 $s_1$ 里，每读完一份 $s_1$ 至少能吃掉 $s_2$ 的一个字符，所以最多扫 $|s_2|$ 份就结束。

第四步：倍增——把"走 $2^k$ 份 $s_2$"预计算出来

只走"份数"次仍然是 $O(c)$，而 $c$ 可以到 $5\times10^7$（例如 $s_1=\texttt{ab}$ 重复 50 次、$s_2=\texttt{ba}$、$n_1=10^6$）。

关键观察：转移是确定性的，所以"匹配 $2^k$ 份 $s_2$"的结果也是确定的，并且可以由两个"$2^{k-1}$ 份"拼出来：

1
2up[0][p] = match_once(p)
up[k][p] = 先走 up[k-1][p]，再在它的落点上走一次 up[k-1]

样例第一组的完整倍增表（$up[k][p]$ 写成 (消耗份数, 落点偏移)）：

读表的要点：$up[2][0]=(4,0)$ 一眼读出"走 4 份 $s_2$ 要吃掉 4 份 $s_1$、落点回到份首"，而这张表只花了两轮拼接就建好了，不需要真走 4 步。

第五步：用二进制拆分挑出最大的 $c$

最后从最大的 $k$ 往小试，能加就加：

1
2
3
4
5used, p, copies = 0, 0, 0
对 k 从大到小：
    blocks, q = up[k][p]
    need = used + blocks + (q > 0)      # 落点不在份首时，当前这一份 s1 也被占用
    若 need <= n1：  used, p, copies = used + blocks, q, copies + 2^k

判据里 used 是此前已经完整跨过的 $s_1$ 份数，blocks 是这一步跨过的份数，最后一项 $[q>0]$ 表示落点不在份首时，当前这一份 $s_1$ 也被占用了一部分，必须算进预算。

样例第一组的挑选过程：$k=2$ 时走 4 份只需 4 份 $s_1$（$q=0$），采纳；再试 $k=1$ 需要 $4+2=6>4$ 份，$k=0$ 需要 $4+1=5>4$ 份，都放弃。于是 $c=4$，$m=\lfloor4/2\rfloor=2$。

$[q>0]$ 这一项在落点不回到份首时才会生效，看一组对照（$s_1=\texttt{abc}$，$s_2=\texttt{ca}$，$n_1=3$）：

$up[1][0]=(2,1)$ 的意思是"跨过 2 份 $s_1$、落回第 3 份的偏移 1"，所以这两份 $s_2$ 实际占住了第 3 份 $s_1$，$c=2$ 而不是 4。这就是判据必须加 $[q>0]$ 的原因。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 最大重复：s2 作为子序列在 conn(s1, n1) 中的最大重复次数，贪心 + 倍增状态。
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>

typedef long long ll;

struct St {
    ll blocks; // 跨过的完整 s1 份数
    ll pos;    // 下一份内的起点
};

std::string s1, s2;
ll L1, L2;

// 从 s1 的下标 p 出发贪心匹配一整份 s2
St match_once(ll p) {
    ll j = 0;
    ll blocks = 0, pos = p;
    while (j < L2) {
        if (s1[pos] == s2[j]) j++;
        pos++;
        if (pos == L1) { // 走完一份 s1，落到下一份的开头
            pos = 0;
            blocks++;
        }
    }
    St r;
    r.blocks = blocks;
    r.pos = pos;
    return r;
}

ll bit_length(ll x) {
    ll c = 0;
    while (x) {
        c++;
        x >>= 1;
    }
    return c;
}

// 返回 s2 作为子序列最多能在 conn(s1, n1) 中出现多少次
ll max_copies(ll n1) {
    bool has[256];
    for (int i = 0; i < 256; i++) has[i] = false;
    for (ll i = 0; i < L1; i++) has[(int)(unsigned char)s1[i]] = true;
    for (ll i = 0; i < L2; i++) {
        if (!has[(int)(unsigned char)s2[i]]) return 0; // 有字符不在 s1 里，一份都放不下
    }

    std::vector<St> base(L1);
    for (ll p = 0; p < L1; p++) base[p] = match_once(p);

    ll LOG = bit_length(n1 * L1 / L2 + 1);
    if (LOG < 1) LOG = 1;
    std::vector<std::vector<St> > up(LOG);
    up[0] = base;
    for (ll k = 1; k < LOG; k++) {
        up[k].assign(L1, St());
        for (ll p = 0; p < L1; p++) {
            St a = up[k - 1][p];
            St b = up[k - 1][a.pos];
            up[k][p].blocks = a.blocks + b.blocks;
            up[k][p].pos = b.pos;
        }
    }

    ll used = 0, p = 0, copies = 0;
    for (ll k = LOG - 1; k >= 0; k--) { // 从大步到小步，能加就加
        St a = up[k][p];
        ll need = used + a.blocks + (a.pos > 0 ? 1 : 0); // 落点不在份首时当前这一份也被占用
        if (need <= n1) {
            used += a.blocks;
            p = a.pos;
            copies += 1LL << k;
        }
    }
    return copies;
}

int main() {
    std::vector<std::string> tok;
    std::string t;
    while (std::cin >> t) tok.push_back(t);
    // 输入末尾可能粘着一个 '}'，它不是字符串内容
    if (!tok.empty() && tok.back() == "}") tok.pop_back();

    for (size_t g = 0; g + 3 < tok.size(); g += 4) {
        s2 = tok[g];
        ll n2 = atoll(tok[g + 1].c_str());
        s1 = tok[g + 2];
        ll n1 = atoll(tok[g + 3].c_str());
        L1 = (ll)s1.size();
        L2 = (ll)s2.size();
        // conn(s2, n2) 重复 m 次就是 s2 重复 m * n2 次
        printf("%lld\n", max_copies(n1) / n2);
    }
    return 0;
}

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#!/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-01 21:33
# update_at: 2026-10-01 21:52

import sys


def match_once(p: int, s1: bytes, s2: bytes) -> tuple[int, int]:
    """从 s1 的下标 p 出发贪心匹配一整份 s2，返回（跨过的完整 s1 份数, 下一份内的起点）。

    每读满一份 s1 至少吃掉 s2 的一个字符（否则该字符根本不在 s1 里，会死循环），
    所以最多扫过 len(s2) 份 s1；调用方必须先用字符集检查排除无解情况。
    """
    j = 0                    # s2 中下一个待匹配的字符
    blocks, pos = 0, p
    while j < len(s2):
        if s1[pos] == s2[j]:
            j += 1
        pos += 1
        if pos == len(s1):   # 走完一份 s1，落到下一份的开头
            pos, blocks = 0, blocks + 1
    return blocks, pos


def max_copies(s1: bytes, s2: bytes, n1: int) -> int:
    """返回 s2 作为子序列最多能在 conn(s1, n1) 中出现多少次（贪心 + 倍增）。"""
    if not set(s2) <= set(s1):
        return 0                                     # s2 有字符不在 s1 里，一份都放不下

    L1 = len(s1)
    L2 = len(s2)
    # base[p]：从一份 s1 的下标 p 出发匹配完一份 s2，消耗的完整 s1 份数与落点。
    # 匹配是确定性的，所以「走 c 份 s2 后的状态」唯一，可以对状态做倍增。
    base = [match_once(p, s1, s2) for p in range(L1)]
    LOG = (n1 * L1 // L2 + 1).bit_length()           # 份数上限的二进制位数，够倍增到它
    up = [base]
    for _ in range(1, LOG):
        prev = up[-1]
        nxt: list[tuple[int, int]] = []
        for p in range(L1):
            blocks, q = prev[p]                      # 先走 2^(k-1) 份 s2，落在偏移 q
            more, q2 = prev[q]                       # 再走 2^(k-1) 份 s2
            nxt.append((blocks + more, q2))
        up.append(nxt)

    used, p, copies = 0, 0, 0
    for k in reversed(range(LOG)):                   # 从大步到小步，能加就加
        blocks, q = up[k][p]
        need = used + blocks + (q > 0)               # 落点不在份首时，当前这一份 s1 也被占用
        if need <= n1:
            used, p, copies = used + blocks, q, copies + (1 << k)
    return copies


def solve() -> None:
    raw = sys.stdin.buffer.read().rstrip()  # 输入末尾可能粘着一个 '}'（不是字符串内容），先把空格换行退掉
    data = raw.removesuffix(b'}').split()
    out: list[str] = []
    for group in range(0, len(data), 4):                 # 每组固定 4 个 token
        s2, n2, s1, n1 = data[group: group + 4]          # 题面的顺序：先 s2 n2，再 s1 n1
        # conn(s2, n2) 重复 m 次就是 s2 重复 m * n2 次，故 m = 最多份数 // n2
        out.append(str(max_copies(s1, s2, int(n1)) // int(n2)))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

设 $L_1=|s_1|$、$L_2=|s_2|$，$c$ 是能放下的份数（上界 $\lfloor n_1L_1/L_2\rfloor\leqslant10^8$）。

• 预处理 base：$O(L_1^2L_2)$，$L_1,L_2\leqslant100$ 时约 $10^6$ 次字节索引；
• 倍增建表与挑选：$O(L_1\log c)$，其中 $\log c\leqslant27$；
• 每组总计 $O(L_1^2L_2+L_1\log c)$，空间 $O(L_1\log c)$。

对比朴素扫描的 $O(n_1L_1)=O(10^8)$，倍增把"重复 $n_1$ 次的同一段"折叠成了 $\log$ 次查表。

总结

• 由 $conn(conn(s_2,n_2),m)=conn(s_2,m\,n_2)$ 把答案化为 $m=\lfloor c/n_2\rfloor$，问题变成"数出 $s_2$ 在 $conn(s_1,n_1)$ 里最多能不重叠出现多少次"。
• 贪心匹配（能匹配就匹配）保证最优；把一份 $s_2$ 的匹配压缩成"份内偏移 → (消耗份数, 落点偏移)"的确定性转移。
• 转移确定性 $\Rightarrow$ 可以倍增：up[k] 由 up[k-1] 自拼得到，于是用二进制拆分在 $O(\log c)$ 内求出 $c$。
• 判据是占用份数 need = used + blocks + (q > 0) <= n1，落点不在份首时不能漏掉当前这一份。

图示解析

下图左侧是一份 $s_2$ 的确定性状态转移（样例第一组），右侧是倍增表的自拼方式与二进制挑选过程。

读图要点：

1. 每个"份内偏移"只有一条出边，边权是吃掉几份 $s_1$——这正是"路线唯一、可倍增"的来源；
2. up[1] = up[0] ∘ up[0]、up[2] = up[1] ∘ up[1]，走 $2^k$ 份 $s_2$ 的答案一步都不用真走；
3. 挑选时先试大步再试小步，绿色表示采纳（占用份数不超 $n_1$），灰色表示超出；样例中只有 $k=2$ 被采纳，得到 $c=4$、$m=2$。