[Solution] Color with Occurrences solution codeforces

Color with Occurrences solution codeforces – You are given some text 𝑡t and a set of 𝑛n strings 𝑠1,𝑠2,,𝑠𝑛s1,s2,…,sn.

In one step, you can choose any occurrence of any string 𝑠𝑖si in the text 𝑡t and color the corresponding characters of the text in red. For example, if 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa and 𝑠1=𝚋𝚊s1=ba𝑠2=𝚊𝚋𝚊s2=aba, you can get 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa or 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa in one step.

Table of Contents

[Solution] Color with Occurrences solution codeforces

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 𝑡[24]=𝑠2=𝚊𝚋𝚊t[2…4]=s2=aba in red, we get 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa;
  • Let’s color 𝑡[12]=𝑠1=𝚋𝚊t[1…2]=s1=ba in red, we get 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa;
  • Let’s color 𝑡[46]=𝑠2=𝚊𝚋𝚊t[4…6]=s2=aba in red, we get 𝑡=𝚋𝚊𝚋𝚊𝚋𝚊t=bababa.

Each string 𝑠𝑖si 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.

[Solution] Color with Occurrences solution codeforces

The first line of the input contains an integer 𝑞q (1𝑞1001≤q≤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|𝑡|1001≤|t|≤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𝑛101≤n≤10) — the number of strings in the set.

This is followed by 𝑛n lines, each containing a string 𝑠𝑖si (1|𝑠𝑖|101≤|si|≤10) consisting only of lowercase Latin letters, where |𝑠𝑖||si| — the length of string 𝑠𝑖si.

Output

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.

[Solution] Color with Occurrences solution codeforces

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: 𝑤𝑗wj and 𝑝𝑗pj (1𝑗𝑚1≤j≤m), which denote that the line with index 𝑤𝑗wj was used as a substring to cover the occurrences starting in the text 𝑡t from position 𝑝𝑗pj. The pairs can be output in any order.

If there are several answers, output any of them.

Example
input

Copy
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

[Solution] Color with Occurrences solution codeforces

output

Copy
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
Note

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.

For Solution

Click Here

Leave a Comment