Color with Occurrences

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

字符串出现转区间覆盖 + 每步取能延伸最远的区间 + 记录选择回溯方案

OJ: codeforces

题目 ID: 1714D

难度:1600

标签:贪心动态规划字符串

创建: 2026-11-09 14:51

更新: 2026-11-10 10:40

前置题目

luogu P2684搞清洁本题的直接前置题。P2684 是赤裸裸的最少区间覆盖问题（直接给出区间求覆盖整条时间轴），本题在此基础上叠加了「在原串中定位子串出现位置转化为区间」以及「记录选取的子串编号与起始下标以还原方案」

前置阅读

区间覆盖：每次把边界推得最远本题把子串匹配转成区间后，核心是经典的「最少区间覆盖」贪心，先看这篇里区间覆盖的完整原理、从第一个缺口出发在候选区间中选右端点最远者的贪心证明与单调指针扫描写法

形式化题目

给定一个字符串 $t$ 和 $n$ 个字符串 $s_1, s_2, \dots, s_n$ 。下标一律从 $0$ 开始。

一次操作：选一个字符串编号 $w$ 和 $t$ 的一个起始位置 $p$ ，要求 $t[p \dots p+|s_w|-1] = s_w$ ，再把半开区间 $[p, p+|s_w|)$ 内的字符全部标红。同一个 $s_w$ 可用任意多次，不同区间是否重叠不作限制。

目标是用最少的操作次数让 $t$ 的每个位置都被标红（即覆盖整个半开区间 $[0, |t|)$ ），并给出每一步选的 $w$ 与 $p$ 。若无法覆盖全部位置，输出 $-1$ 。

解法总览

题目规模很小（ $|t| \leqslant 100$ ， $n \leqslant 10$ ），难点不在算法复杂度，而在把“涂红”这件事转成正确的组合模型。两种解法建立在同一个观察上，区别只在如何推进。

把每个 $s_i$ 在 $t$ 中的每一次出现看成一个能“一步整段涂红”的半开区间 $[l, r)$ （其中 $r = l + |s_i|$ ）。那么“把 $t$ 全涂红”等价于“用这些区间的并集盖满半开区间 $[0, |t|)$ ”。每个区间代价都是 $1$ ，问题就是经典的“最少区间覆盖整段”。采用半开区间的好处在于：子串长度就是右端点与左端点之差，覆盖状态直接对齐光标下标，不需要任何 $\pm 1$ 的换算。

解法	核心观察	复杂度	适用场景	对应代码
解法一：贪心	从左往右推进，每步在左端点已被覆盖的区间里取能延伸最远的右端点	$O(n\lvert t\rvert^2)$	只求最少步数、顺带记录方案，实现最短	`main.cpp`、`main.py`
解法二：DP	以“已涂红前缀长度”为状态，逐层推进能到达的最远前缀	$O(n\lvert t\rvert^2)$	需要最短路式建模、方案回溯更稳妥	`main2.cpp`、`main2.py`

两者答案必然相同。每个区间代价都是 $1$ ，贪心里“取最远右端点不劣”这条性质，正是 DP 中可以把较短前缀的状态直接合并到较长前缀上的依据。正式主解取贪心 main.cpp，它对本题最直接、代码最少。

解法一：贪心（最少区间覆盖整段）

从待覆盖光标出发，每步选能延伸最远的半开区间。

把每个 $s_i$ 的每次出现变成半开区间 $[l, r)$ （ $r = l + |s_i|$ ）。维护光标 $\text{cur}$ 表示 $[0, \text{cur})$ 已全红，下一个必须被染红的位置就是 $\text{cur}$ 。在所有覆盖 $\text{cur}$ （即 $l \leqslant \text{cur} < r$ ）的候选区间中，选择右开端点 $r$ 最大的那个涂上它，并将光标直接推进到 $\text{cur} \leftarrow r$ ，同时记录其 $w$ 与 $p$ 。重复直到 $\text{cur} = |t|$ 。若某一步没有任何区间的右端点能超过 $\text{cur}$ （即断层），输出 $-1$ 。正确性基于贪心交换：任何可行解都必须有区间跨过当前光标，换成能延伸最远者必不劣。

思路

落成区间覆盖之后，问题就是选最少的区间盖住半开区间 $[0, |t|)$ 。

相比全闭区间 $[l, r]$ ，半开区间 $[l, r)$ 在思考与实现上心智负担更低：

子串从下标 $p$ 开始、长为 $|s_w|$ ，其半开区间右端点自然是 $r = p + |s_w|$ ，与字符串切片直觉一致，不需要 $-1$ ；
我们用一个光标 $\text{cur}$ 表示当前进度：前缀 $[0, \text{cur})$ 已经全红，下一个必须被覆盖的字符下标正是 $\text{cur}$ ；
推进时，选定右端点为 $r$ 的区间后，覆盖范围直接扩展到 $[0, r)$ ，下一步光标直接是 $\text{cur} \leftarrow r$ ，不需要 $+1$ 。

任何可行解都必须有一个区间覆盖当前光标 $\text{cur}$ ，否则该位置永远涂不红。既然必须覆盖 $\text{cur}$ ，那么在所有满足 $l \leqslant \text{cur} < r$ 的区间里，右端点 $r$ 最大的那个向右延伸最远，绝不会让后续决策变差。这就是贪心选择的正确性所在。

算法流程很直接：

预处理找出所有子串匹配，得到半开区间集合 $(l, r, w, p)$ ，其中 $r = l + |s_w|$ ；
初始化 $\text{cur} \leftarrow 0$ ；
当 $\text{cur} < |t|$ 时，在所有满足 $l \leqslant \text{cur}$ 的区间里寻找 $r$ 最大的区间：
- 若最大的 $r \leqslant \text{cur}$ ，说明当前位置无法被任何可用区间越过（出现断层），输出 $-1$ ；
- 否则记录方案 $(w, p)$ ，并将光标更新为 $\text{cur} \leftarrow r$ 。

这里的候选条件是“ $l \leqslant \text{cur}$ ”，而不是要求恰好接缝“ $l = \text{cur}$ ”。题目允许区间重叠，一个区间完全可以从更早的已涂红区域起步，只要其右端点能跨过当前光标并向右延伸即可。

代码

同一算法的 C++ 与 Python 实现，逻辑一致。

C++ 版本：

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/**
 * 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-11-09 17:35
 * update_at: 2026-11-09 22:39
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

// 区间结构体：记录字符串匹配出的一个可用线段，采用半开区间 [l, r)
struct Segment {
    int l;   // 区间左端点（0-indexed）
    int r;   // 区间右开端点（0-indexed，覆盖 [l, r)）
    int id;  // 对应第几个字符串（1-indexed）
    int pos; // 在原串 t 中的起始位置（1-indexed）
};

// 操作方案记录
struct Operation {
    int id;
    int pos;
};

int n;
string t;
string s[MAXN];

vector<Segment> segs;     // 存储所有匹配出来的区间
vector<Operation> ans;    // 存储最终选择的操作步骤

void read_input() {
    cin >> t >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
}

// 预处理：利用 string::find 找出所有字符串在文本 t 中的出现区间 [left, right)
void build_segments() {
    segs.clear();
    for (int i = 1; i <= n; i++) {
        int len_s = s[i].size();
        size_t p = t.find(s[i], 0);
        while (p != string::npos) {
            int left = p;
            int right = left + len_s; // 半开区间右端点：无需减 1
            segs.push_back({left, right, i, left + 1});
            p = t.find(s[i], p + 1); // 允许重叠，从 p + 1 继续寻找下一个出现位置
        }
    }
}

void solve() {
    build_segments();
    ans.clear();

    int len_t = t.size();
    int cur = 0; // 当前待覆盖的起始位置，即 [0, cur) 已全部被染红

    // 每次在所有覆盖 cur（l <= cur < r）的区间里，选择右端点 r 最大的那一个
    while (cur < len_t) {
        int max_r = -1;
        Segment best_seg;

        for (const auto &seg : segs) {
            if (seg.l <= cur && seg.r > max_r) {
                max_r = seg.r;
                best_seg = seg;
            }
        }

        // 如果找不到任何能延伸超过 cur 的区间，说明出现断层，无解
        if (max_r <= cur) {
            cout << -1 << "\n";
            return;
        }

        ans.push_back({best_seg.id, best_seg.pos});
        cur = max_r; // 直接推进到新的右边界，无需加 1
    }

    cout << ans.size() << "\n";
    for (const auto &op : ans) {
        cout << op.id << " " << op.pos << "\n";
    }
}

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

    int q;
    if (cin >> q) {
        while (q--) {
            read_input();
            solve();
        }
    }
    return 0;
}

Python 版本：

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-11-09 17:35
# update_at: 2026-11-10 10:25

import sys
from collections.abc import Iterator

# 匹配区间：(左端点 l, 右端点 r, 单词序号 w, 1 起起始位置 p)，半开区间 [l, r)
type Match = tuple[int, int, int, int]
type Plan = list[tuple[int, int]]


def occurrences(t: str, s: str) -> Iterator[int]:
    """产出子串 s 在 t 中的所有起始位置（允许重叠）。"""
    p = t.find(s)
    while p != -1:
        yield p
        p = t.find(s, p + 1)


def min_color(t: str, words: list[str]) -> Plan | None:
    """计算将 t 涂红的最少区间方案；若无法涂满返回 None。"""
    matches: list[Match] = [
        (p, p + len(s), w, p + 1)
        for w, s in enumerate(words, 1)
        for p in occurrences(t, s)
    ]

    cur, plan = 0, []
    while cur < len(t):
        valid = [(r, w, p) for l, r, w, p in matches if l <= cur < r]
        if not valid:
            return None
        r, w, p = max(valid)  # 贪心选择右开端点 r 最大的区间
        plan.append((w, p))
        cur = r

    return plan


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    q = int(next(data))

    for _ in range(q):
        t = next(data).decode()
        n = int(next(data))
        words = [next(data).decode() for _ in range(n)]

        plan = min_color(t, words)
        if plan is None:
            out.append("-1")
        else:
            out.append(str(len(plan)))
            out.extend(f"{w} {p}" for w, p in plan)

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

区间总数 $O(n|t|)$ ，生成并排序 $O(n|t| \log(n|t|))$ 。贪心循环最多 $|t|$ 步，每步扫一遍区间 $O(n|t|)$ 。总时间 $O(n|t|^2)$ ，空间 $O(n|t|)$ 。 $n \leqslant 10, |t| \leqslant 100$ 时量级在 $10^6$ ，远低于限制。

解法二：DP（覆盖前缀的最少步数）

以“已涂红前缀长度”为状态，采用推模式 DP 逐层向后更新。

令 $dp[i]$ 为涂红半开前缀 $[0,i)$ 的最少步数， $dp[0]=0$ 。采用推模式 DP：以当前已知状态 $i$ 为起点，枚举每一个覆盖断口 $i$ 的可用区间 $[l, r)$ （满足 $l \leqslant i < r$ ），将其能扩展到的新前缀终点设为 $\text{reach} = r$ 。主动更新后继状态 $dp[\text{reach}]=\min(dp[\text{reach}], dp[i]+1)$ ，并用前驱数组记下这一步转移用的 $w,p$ 。若 $dp[|t|]$ 仍是无穷大则无解，否则从 $|t|$ 沿前驱回溯出方案。

思路

贪心每步只保留“最远右端点”一个状态，这是把问题压缩后的结果。与其一开始就相信这个压缩，不如保留所有可能的前缀终点，用 DP 把方案空间完整扫一遍，答案自然浮现，方案也好回溯。

状态定义

涂红过程是单调向右扩张的：一旦前缀 $[0,i)$ 全红，“红到哪”只需要一个数 $i$ （即半开前缀长度）表示，内部哪些区间重叠过并不重要。

定义 $dp[i]$ 表示将半开区间 $[0, i)$ 全部涂红所需的最少步数，起点 $dp[0]=0$ （尚未涂红任何字符时步数为 $0$ ）。

转移方程：推模式 DP

本题采用推模式 DP（Push DP，即“刷表法”）：不是站在后继点去拉取前驱，而是用当前已确定的前缀点 $i$ 主动去更新后面的点 $j$ （即 $\text{reach}$ ）。

当遍历到当前位置 $i$ 且 $dp[i]$ 可达时，任取一个覆盖了当前断点 $i$ 的半开匹配区间 $[l, r)$ （要求 $l \leqslant i < r$ ）。该区间左侧落在已红区域内（允许重叠），右侧越过了断口 $i$ ，因此能将染红前缀一口气向右推进到 $\text{reach} = r$ 。由此产生向后推进的状态转移：

dp[\text{reach}] = \min\bigl(dp[\text{reach}],\; dp[i] + 1\bigr).

图示清晰展现了这一推模式 DP 的核心思想：

当前点 $i$ 作为发射源：已知 $[0, i)$ 的最优代价为 $dp[i]$ ；
区间 $[l, r)$ 作为跳板：只要 $l \leqslant i < r$ ，区间就能无缝跨过当前必须染红的位置 $i$ ；
后继点 $\text{reach} = r$ 被主动刷新：用 $dp[i] + 1$ 的代价去松弛 $dp[\text{reach}]$ ，并记录转移前驱。

把 $i$ 从 $0$ 到 $|t|-1$ 顺次推进，每个可达的 $i$ 枚举所有匹配区间做转移。用 pre[] 记下每个后继状态是由哪个前驱 $i$ 与哪次操作推进而来的，最后从 $|t|$ 沿前驱回溯，即得到全局最优涂红方案。

用样例 $t=\texttt{bababa}$ 、 $s_1=\texttt{ba}$ 、 $s_2=\texttt{aba}$ 走一遍。可用半开区间为 ba 的 $[0,2),[2,4),[4,6)$ 与 aba 的 $[1,4),[3,6)$ ，下表给出 $dp$ 被有效更新的过程：

当前前缀点 $i$	当前 $dp[i]$	选用区间 $[l,r)$	推进到的后继点 $\text{reach}$	更新结果
$0$	$0$	$[0,2)$	$2$	$dp[2]=1$
$2$	$1$	$[1,4)$	$4$	$dp[4]=2$
$4$	$2$	$[3,6)$	$6$	$dp[6]=3$

最终 $dp[6]=3$ ，与样例的最少步数一致；沿 pre[] 回溯得到的三步正好对应上表的三行。

若最终 $dp[|t|]$ 仍是无穷大，说明有位置涂不到，输出 $-1$ 。

代码

同一算法的 C++ 与 Python 实现，逻辑一致。

C++ 版本：

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/**
 * 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-11-09 17:35
 * update_at: 2026-11-09 22:39
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const int INF = 1e9;

// 区间结构体：记录字符串匹配出的一个可用线段
struct Segment {
    int l;   // 区间左端点（0-indexed）
    int r;   // 区间右端点（0-indexed）
    int id;  // 对应第几个字符串（1-indexed）
    int pos; // 在原串 t 中的起始位置（1-indexed）
};

// 状态前驱记录：用于回溯最优方案
struct Step {
    int prev_idx; // 上一个状态位置
    int id;       // 本次使用的字符串编号
    int pos;      // 本次使用的起始位置
};

int n;
string t;
string s[MAXN];

int dp[MAXN];          // dp[i] 表示完全覆盖前缀 t[0..i-1] 所需的最少操作次数
Step pre[MAXN];        // pre[i] 记录 dp[i] 是从哪个状态转移而来的
vector<Segment> segs;  // 存储所有匹配出来的区间

void read_input() {
    cin >> t >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
}

// 预处理：利用 string::find 找出所有字符串在文本 t 中的所有出现区间（允许重叠）
void build_segments() {
    segs.clear();
    for (int i = 1; i <= n; i++) {
        int len_s = s[i].size();
        size_t p = t.find(s[i], 0);
        while (p != string::npos) {
            int left = p;
            int right = left + len_s - 1;
            segs.push_back({left, right, i, left + 1});
            p = t.find(s[i], p + 1); // 允许重叠，从 p + 1 继续寻找下一个出现位置
        }
    }
}

void solve() {
    build_segments();

    int len_t = t.size();
    for (int i = 0; i <= len_t; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;

    // dp[i]：前缀 [0..i-1] 已经全部覆盖
    for (int i = 0; i < len_t; i++) {
        if (dp[i] == INF) continue;

        // 枚举所有可以接在当前前缀后面的区间（要求区间的左端点落在已覆盖区域内，即 seg.l <= i）
        for (const auto &seg : segs) {
            if (seg.l <= i) {
                int next_idx = max(i, seg.r + 1); // 新覆盖到达的前缀边界
                if (dp[next_idx] > dp[i] + 1) {
                    dp[next_idx] = dp[i] + 1;
                    pre[next_idx] = {i, seg.id, seg.pos};
                }
            }
        }
    }

    // 无法覆盖整串
    if (dp[len_t] == INF) {
        cout << -1 << "\n";
        return;
    }

    // 从终点向前回溯提取方案
    vector<pair<int, int>> ans;
    int cur = len_t;
    while (cur > 0) {
        ans.push_back({pre[cur].id, pre[cur].pos});
        cur = pre[cur].prev_idx;
    }

    // 倒序恢复成从前到后的操作序列
    reverse(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (const auto &op : ans) {
        cout << op.first << " " << op.second << "\n";
    }
}

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

    int q;
    if (cin >> q) {
        while (q--) {
            read_input();
            solve();
        }
    }
    return 0;
}

Python 版本：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#!/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-11-09 17:35
# update_at: 2026-11-10 10:30

import sys
from collections.abc import Iterator

INF = 10**9  # 表示该前缀目前不可达

# 匹配区间：(左端点 l, 右端点 r, 单词序号 w, 1 起起始位置 p)，半开区间 [l, r)
type Match = tuple[int, int, int, int]
# 转移前驱：(上一前缀长度 prev_i, 单词序号 w, 1 起起始位置 p)
type Step = tuple[int, int, int]
type Plan = list[tuple[int, int]]


def occurrences(t: str, s: str) -> Iterator[int]:
    """产出子串 s 在 t 中的所有起始位置（允许重叠）。"""
    p = t.find(s)
    while p != -1:
        yield p
        p = t.find(s, p + 1)


def min_color_dp(t: str, words: list[str]) -> Plan | None:
    """用 DP 计算将 t 涂红的最少区间方案；若无法涂满返回 None。"""
    matches: list[Match] = [
        (p, p + len(s), w, p + 1)
        for w, s in enumerate(words, 1)
        for p in occurrences(t, s)
    ]

    n = len(t)
    # dp[i] 表示染红前缀 [0, i) 所需的最少操作步数
    dp = [0] + [INF] * n
    pre: list[Step | None] = [None] * (n + 1)

    for i in range(n):
        if dp[i] == INF:
            continue
        cost = dp[i] + 1
        for l, r, w, p in matches:
            # 区间覆盖当前末端点 i（l <= i < r），可将前缀延伸到 r
            if l <= i < r and cost < dp[r]:
                dp[r] = cost
                pre[r] = (i, w, p)

    if dp[n] == INF:
        return None

    # 从终点 n 沿前驱回溯最优路径
    plan: Plan = []
    cur = n
    while cur > 0:
        assert pre[cur] is not None
        cur, w, p = pre[cur]
        plan.append((w, p))

    return plan[::-1]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    q = int(next(data))

    for _ in range(q):
        t = next(data).decode()
        n = int(next(data))
        words = [next(data).decode() for _ in range(n)]

        plan = min_color_dp(t, words)
        if plan is None:
            out.append("-1")
        else:
            out.append(str(len(plan)))
            out.extend(f"{w} {p}" for w, p in plan)

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

状态数 $O(|t|)$ ，每个状态枚举区间 $O(n|t|)$ ，时间 $O(n|t|^2)$ 。额外记录映射关系，空间 $O(|t|)$ （区间表 $O(n|t|)$ ）。与贪心同阶。

复杂度对比

解法	时间	空间	方案回溯
贪心	$O(n\lvert t\rvert^2)$	$O(n\lvert t\rvert)$	边推进边记录
DP	$O(n\lvert t\rvert^2)$	$O(\lvert t\rvert)$	前驱数组回溯

两种解法复杂度相同，因为本题规模本就很小。选贪心是因为它最短、最贴合“区间覆盖”的直觉；选 DP 是因为状态定义清晰、方案回溯不易出错。若把数据放大到 $|t|=10^5$ ，只要把“每步扫一遍区间”换成“按左端点预处理 + 预扫最大右端点”，贪心就能降到 $O(|t| + n|t|)$ ，而 DP 的思路不变。

总结

这题的转折是把“涂红字符”翻译成“选区间覆盖整段”：每个 $s_i$ 的每次出现都是一个代价为 $1$ 的区间，目标就是最少区间覆盖。

在此基础上两条路都成立：

贪心：当前位置必须被某个区间跨过，选能延伸最远的那个不会让后续变差，于是每步取最远右端点；
DP：把“已涂红前缀长度”当状态，逐层推进到能到达的最远前缀，方案回溯更直观。

两个容易写错的地方：

采用半开区间 $[l, r)$ 思考与实现，状态从头到尾对齐待覆盖光标 $\text{cur}$ ，免除 $\pm 1$ 的差一边界；
允许区间重叠，所以候选区间的左端点用 $l \leqslant \text{cur}$ （DP 里是 $l \leqslant i$ ），而不是要求恰好接缝；
找不到任何能越过当前位置的区间时（ $r_{\max} \leqslant \text{cur}$ ）输出 $-1$ ，别漏判无解。

1714D Color with Occurrences

题目描述

给定一段文本 $t$ 和一组 $n$ 字符串 $s_1, s_2, \dots, s_n$ 。

在每一步操作中，你可以选择文本 $t$ 中任意出现的字符串 $s_i$ ，并将文本中对应的字符标记为红色。例如，若 $t=\texttt{bababa}$ 且 $s_1=\texttt{ba}$ ， $s_2=\texttt{aba}$ ，则通过一步操作可以得到 $t=\color{red}{\texttt{ba}}\texttt{baba}$ 、 $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ 或 $t=\texttt{bab}\color{red}{\texttt{aba}}$ 。

你需要将文本 $t$ 的所有字母都标记为红色。当某个字母被重复标记时，其红色状态保持不变。

在上例中，只需三步即可完成：

首先标记 $t[2 \dots 4]=s_2=\texttt{aba}$ 为红色，得到 $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ ；
接着标记 $t[1 \dots 2]=s_1=\texttt{ba}$ 为红色，得到 $t=\color{red}{\texttt{baba}}\texttt{ba}$ ；
最后标记 $t[4 \dots 6]=s_2=\texttt{aba}$ 为红色，得到 $t=\color{red}{\texttt{bababa}}$ 。

每个字符串 $s_i$ 可以被使用任意次数（或完全不使用）。标记时的字符串出现位置可以任意重叠。

请确定将所有字母 $t$ 标记为红色所需的最少操作步数及具体方案。若无法将文本 $t$ 的所有字母标红，则输出-1。

输入格式

输入第一行包含整数 $q$ （ $1 \le q \le 100$ ）——表示测试用例的数量。

接下来描述每个测试用例。

每个测试用例的第一行包含文本 $t$ （ $1 \le |t| \le 100$ ），该文本仅由小写拉丁字母组成，其中 $|t|$ 表示文本 $t$ 的长度。

第二行包含一个整数 $n$ （ $1 \le n \le 10$ ）——表示字符串集合中的字符串数量。

随后 $n$ 行，每行包含一个字符串 $s_i$ （ $1 \le |s_i| \le 10$ ），这些字符串仅由小写拉丁字母组成，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。

输出格式

对于每个测试用例，在单独一行输出答案。

若无法将所有字母标红，则输出一行包含数字-1。

否则，第一行输出数字 $m$ ——表示将所有字母 $t$ 标红所需的最少操作步数。

接下来的 $m$ 行输出索引对： $w_j$ 和 $p_j$ （ $1 \le j \le m$ ），表示使用索引为 $w_j$ 的字符串作为子串，覆盖文本 $t$ 中从位置 $p_j$ 开始的出现位置。这些索引对可以按任意顺序输出。

若存在多种可行方案，输出其中任意一种即可。

提示

第一个测试用例的说明已在题目描述中给出。

在第二个测试用例中，无法将所有字母标红。

输入输出样例 #1

输入 #1

text

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
316
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb

输出 #1