题目大意：给出一个文章t和n个字符串s1,s2...sn；
问能否用这n个字符串将整个文章覆盖；
思路：贪心（最小区间覆盖)
记录每个字符串能够覆盖的所有位置（起点，终点，编号)
排序后贪心的求出是否能够将所有点覆盖
1 # include<iostream>
2 # include<bits/stdc++.h>
3 using namespace std;
4 # define int long long
5 # define endl "\n"
6 const int N = 2e5 + 10, INF = 0x3f3f3f3f3f;
7 struct node {
8 int l, r, id;//起点，终点，编号
9 };
10 string s;
11 bool cmp(node a, node b) {
12 if (a.l != b.l) return a.l < b.l;
13 return a.r < b.r;
14 }
15 vector<node> se;
16 int length;
17
18 bool check(int start, string t) {
19 int maxv = length - start + 1;
20 if (maxv < t.size()) return false;
21 for (int i = start, j = 0; i <= start + t.size() - 1; ++i, ++j) {
22 if (t[j] != s[i]) return false;
23 }
24 return true;
25 }
26
27 void solve() {
28
29 int n;
30 cin >> s >> n;
31 se.clear();
32 length = s.size();
33 s = "?" + s;
34 for (int i = 1; i <= n; ++i) {
35 string t;
36 cin >> t;
37 int len = t.size();
38 for (int j = 1; j <= length; ++j) {
39 if (check(j, t)) se.push_back({j, j + len - 1, i});//记录每个字符串能够覆盖的点
40 }
41 }
42 sort(se.begin(), se.end(), cmp);//以起始点为基准从小到大排序
43 bool ok = false;
44 int start = 1, ed = length;
45 vector<pair<int, int>> ans;
46 for (int i = 0; i < se.size(); ++i) {
47 int j = i, r = -INF;
48
49 int t = 0;
50 while (j < se.size() && se[j].l <= start) {
51 if (se[j].r > r) //寻找能够覆盖区间最长的字符串
{
52 r = se[j].r;
53 t = j;
54 }
55 j++;
56 }
57 if (r < start) break;
58 start = r+1,i = j-1;
59 ans.push_back({se[t].id,se[t].l});
60 if(r>= ed){
61 ok = true;
62 break;
63 }
64 }
65 if(ok){
66 cout<<ans.size()<<endl;
67 for(auto it:ans)cout<<it.first<<" "<<it.second<<endl;
68 }
69 else cout<<-1<<endl;
70 }
71 int tt;
72 signed main() {
73 ios::sync_with_stdio(false);
74 cin.tie(0);
75 cout.tie(0);
76 cin >> tt;
77 while (tt--)solve();
78
79
80 return 0;
81 }
