Color with Occurrences

题意翻译

给定一段黑色文本 $t$ 和多个字符串 $s_1,s_2...s_n$。 一次操作可以将 $t$ 中任意一个与任意 $s$ 相等的子串涂成红色。两次涂红的字母仍然是红色。$s$ 没有使用次数限制。求全涂成红色最小次数和方案，任意输出一种解。 一共有 $q$ 组测试数据。 举例： $ t=\texttt{bababa} \ \ s_1=\texttt{ba} $ , $ s_2=\texttt{aba} $ 一步可以得到 $ t=\color{red}{\texttt{ba}}\color{black}\texttt{baba} $ , $ t=\texttt{b}\color{red}{\texttt{aba}}\color{black}\texttt{ba} $ or $ t=\texttt{bab}\color{red}{\texttt{aba}} $ 中的一个。 全部涂黑所需 $3$ 步如下： - 涂红 $ t[2 \dots 4]=s_2=\texttt{aba} $ 得 $ t=\texttt{b}\color{red}\texttt{aba}\color{black}\texttt{ba} $ ; - 涂红 $ t[1 \dots 2]=s_1=\texttt{ba} $ 得 $ t=\color{red}\texttt{baba}\color{black}\texttt{ba} $ ; - 涂红 $ t[4 \dots 6]=s_2=\texttt{aba} $ 得 $ t=\color{red}{\texttt{bababa}} $ .

题目描述

You are given some text $ t $ and a set of $ n $ strings $ s_1, s_2, \dots, s_n $ . In one step, you can choose any occurrence of any string $ s_i $ in the text $ t $ and color the corresponding characters of the text in red. For example, if $ t=\texttt{bababa} $ and $ s_1=\texttt{ba} $ , $ s_2=\texttt{aba} $ , you can get $ t=\color{red}{\texttt{ba}}\texttt{baba} $ , $ t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba} $ or $ t=\texttt{bab}\color{red}{\texttt{aba}} $ in one step. You want to color all the letters of the text $ t $ in red. When you color a letter in red again, it stays red. In the example above, three steps are enough: - Let's color $ t[2 \dots 4]=s_2=\texttt{aba} $ in red, we get $ t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba} $ ; - Let's color $ t[1 \dots 2]=s_1=\texttt{ba} $ in red, we get $ t=\color{red}{\texttt{baba}}\texttt{ba} $ ; - Let's color $ t[4 \dots 6]=s_2=\texttt{aba} $ in red, we get $ t=\color{red}{\texttt{bababa}} $ . Each string $ s_i $ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily. Determine the minimum number of steps needed to color all letters $ t $ in red and how to do it. If it is impossible to color all letters of the text $ t $ in red, output -1.

输入输出格式

输入格式

The first line of the input contains an integer $ q $ ( $ 1 \le q \le 100 $ ) —the number of test cases in the test. The descriptions of the test cases follow. The first line of each test case contains the text $ t $ ( $ 1 \le |t| \le 100 $ ), consisting only of lowercase Latin letters, where $ |t| $ is the length of the text $ t $ . The second line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10 $ ) — the number of strings in the set. This is followed by $ n $ lines, each containing a string $ s_i $ ( $ 1 \le |s_i| \le 10 $ ) consisting only of lowercase Latin letters, where $ |s_i| $ — the length of string $ s_i $ .

输出格式

For each test case, print the answer on a separate line. If it is impossible to color all the letters of the text in red, print a single line containing the number -1. Otherwise, on the first line, print the number $ m $ — the minimum number of steps it will take to turn all the letters $ t $ red. Then in the next $ m $ lines print pairs of indices: $ w_j $ and $ p_j $ ( $ 1 \le j \le m $ ), which denote that the string with index $ w_j $ was used as a substring to cover the occurrences starting in the text $ t $ from position $ p_j $ . The pairs can be output in any order. If there are several answers, output any of them.

输入输出样例

输入样例 #1

6
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

3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13

说明

The first test case is explained in the problem statement. In the second test case, it is impossible to color all the letters of the text in red.

**题目大意：**

题目描述了一个关于字符串的操作问题。给定一个字符串 $ t $ 和一组字符串 $ s_1, s_2, \dots, s_n $。每次操作可以将 $ t $ 中与 $ s $ 相等的任意子串涂成红色。涂红的字母再次被涂红仍然是红色。求将整个字符串 $ t $ 全部涂成红色所需的最小操作次数及方案。如果无法将整个字符串 $ t $ 涂成红色，则输出 -1。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 $ q $（$ 1 \le q \le 100 $），表示测试数据的组数。
- 每组测试数据包含：
- 第一行是一个字符串 $ t $（$ 1 \le |t| \le 100 $），只包含小写拉丁字母。
- 第二行包含一个整数 $ n $（$ 1 \le n \le 10 $），表示字符串 $ s $ 的数量。
- 接下来 $ n $ 行，每行包含一个字符串 $ s_i $（$ 1 \le |s_i| \le 10 $），只包含小写拉丁字母。

**输出格式：**
- 对于每组测试数据，输出一行答案。
- 如果无法将整个字符串 $ t $ 涂成红色，输出 -1。
- 否则，第一行输出一个整数 $ m $，表示将整个字符串 $ t $ 涂成红色所需的最小操作次数。
- 接下来 $ m $ 行，每行输出一对整数 $ w_j $ 和 $ p_j $（$ 1 \le j \le m $），表示第 $ w_j $ 个字符串被用来覆盖从文本 $ t $ 的第 $ p_j $ 个位置开始的子串。输出的对数可以按任意顺序。

**输入输出样例：**
- 输入样例 #1：
```
6
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：
```
3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13
```**题目大意：** 题目描述了一个关于字符串的操作问题。给定一个字符串 $ t $ 和一组字符串 $ s_1, s_2, \dots, s_n $。每次操作可以将 $ t $ 中与 $ s $ 相等的任意子串涂成红色。涂红的字母再次被涂红仍然是红色。求将整个字符串 $ t $ 全部涂成红色所需的最小操作次数及方案。如果无法将整个字符串 $ t $ 涂成红色，则输出 -1。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ q $（$ 1 \le q \le 100 $），表示测试数据的组数。 - 每组测试数据包含： - 第一行是一个字符串 $ t $（$ 1 \le |t| \le 100 $），只包含小写拉丁字母。 - 第二行包含一个整数 $ n $（$ 1 \le n \le 10 $），表示字符串 $ s $ 的数量。 - 接下来 $ n $ 行，每行包含一个字符串 $ s_i $（$ 1 \le |s_i| \le 10 $），只包含小写拉丁字母。 **输出格式：** - 对于每组测试数据，输出一行答案。 - 如果无法将整个字符串 $ t $ 涂成红色，输出 -1。 - 否则，第一行输出一个整数 $ m $，表示将整个字符串 $ t $ 涂成红色所需的最小操作次数。 - 接下来 $ m $ 行，每行输出一对整数 $ w_j $ 和 $ p_j $（$ 1 \le j \le m $），表示第 $ w_j $ 个字符串被用来覆盖从文本 $ t $ 的第 $ p_j $ 个位置开始的子串。输出的对数可以按任意顺序。 **输入输出样例：** - 输入样例 #1： ``` 6 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： ``` 3 2 2 1 1 2 4 -1 4 1 1 2 6 3 3 3 7 4 3 1 1 2 2 3 1 4 2 4 5 2 1 4 3 1 4 5 2 9 1 13 ```