D. Color with Occurrences Codeforces Round #811 (Div. 3)

You are given some text tt and a set of nn strings s1,s2,…,sns1,s2,…,sn.

In one step, you can choose any occurrence of any string sisi in the text tt and color the corresponding characters of the text in red. For example, if t=bababat=bababa and s1=bas1=ba, s2=abas2=aba, you can get t=bababat=bababa, t=bababat=bababa or t=bababat=bababa in one step.

You want to color all the letters of the text tt 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…4]=s2=abat[2…4]=s2=aba in red, we get t=bababat=bababa;
• Let's color t[1…2]=s1=bat[1…2]=s1=ba in red, we get t=bababat=bababa;
• Let's color t[4…6]=s2=abat[4…6]=s2=aba in red, we get t=bababat=bababa.

Each string sisi 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 tt in red and how to do it. If it is impossible to color all letters of the text tt in red, output -1.

Input

The first line of the input contains an integer qq (1≤q≤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 tt (1≤|t|≤1001≤|t|≤100), consisting only of lowercase Latin letters, where |t||t| is the length of the text tt.

The second line of each test case contains a single integer nn (1≤n≤101≤n≤10) — the number of strings in the set.

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

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.

Otherwise, on the first line, print the number mm — the minimum number of steps it will take to turn all the letters tt red.

Then in the next mm lines print pairs of indices: wjwj and pjpj (1≤j≤m1≤j≤m), which denote that the string with index wjwj was used as a substring to cover the occurrences starting in the text tt from position pjpj. The pairs can be output in any order.

If there are several answers, output any of them.

题意：给你一个模板串s，再给你n个子串t，求最小能把s覆盖完的需要的t的数量，不能输出-1

要用到最小区间覆盖问题，如果不了解请先移步我的另一篇最小区间覆盖问题_Demoo.的博客-CSDN博客

思路：先把模板串处理一下，用一个num数组来记录下模板串标为i的地方以i为左端点子串的编号

用一个mx数组来记录一下在下标为i的地方，以i为左端点子串能覆盖的最大长度

然后我们先将mx数组初始化为负数

然后每次输入一个子串的时候我们遍历一遍s字符串的每个下标，找出mx数组和num数组

然后我们处理完之后开始用最小区间覆盖问题

先判断下标为0的地方是不是被覆盖了，如果不是的话直接输出-1

如果是的话，我们记录一下刚开始的区间的左端点为last=0，区间的个数为flag=1

然后我们再遍历的时候就按区间最小覆盖问题来，注意last表示已经覆盖的区间的左端点

last+mx[last]-1表示已经覆盖的区间的右端点

ac码：

/*
 .----------------.  .----------------.  .----------------.  .----------------. 
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ________    | || |  _________   | || | ____    ____ | || |     ____     | |
| | |_   ___ `.  | || | |_   ___  |  | || ||_   \  /   _|| || |   .'    `.   | |
| |   | |   `. \ | || |   | |_  \_|  | || |  |   \/   |  | || |  /  .--.  \  | |
| |   | |    | | | || |   |  _|  _   | || |  | |\  /| |  | || |  | |    | |  | |
| |  _| |___.' / | || |  _| |___/ |  | || | _| |_\/_| |_ | || |  \  `--'  /  | |
| | |________.'  | || | |_________|  | || ||_____||_____|| || |   `.____.'   | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b){
	return b>0 ? gcd(b,a%b):a;
}
const int N=1e3+10;
int n,m;
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
int mx[N];//储存以i为左端点，有子字符串的最大长度
int num[N];//储存以i为左下标开始字符串的序号
vector ans;//储存字符串的序号和开始的下标
const int INF=0x3f3f3f3f;
void sove(){
	ans.clear() ;
	string s;
	cin >> s >> m;
    n = s.size();
    for (int i = 0; i <= n; ++i)    mx[i] = -INF;//把长度初始化
    for (int i = 1; i <= m; ++i) {//每次读入字符串t
    	string t;
        cin >> t;
        for (int j = 0; j < n; ++j) {//然后遍历原字符串s的各个下标来和子串匹配
            int k = 0, nn = t.size();
            while (k < nn && j  + k < n && t[k] == s[j  + k])
                ++k;
            if (k == nn) {//当能与子字符串匹配的话就更新以j为下标的最长长度和字符串的编号
                if (nn > mx[j]) mx[j] = nn, num[j] = i;
            }
        }
    }
/*	for(int i=0;i
		cout<
	}
	cout<
	if(mx[0]==-0x3f3f3f3f){//如果刚开始没有匹配上说明根本就不能涂满
		cout<<-1<
		return ;
	}
	//刚开始的区间能覆盖的话
	int last =0,flag=1;//last来表示已经覆盖区间的左端点，flag表示覆盖的区间的个数
	ans.push_back({num[0],1}); //把刚开始的数的子字符串的编号和坐标加入（从1开始
	for(int i=1;i//遍历整个区间
	/*	cout<
		cout<
		//mx[i]+i-1表示以i为左端点子串的右端点
		if(i<=last+mx[last]-1+1&&i+mx[i]-1>last+mx[last]-1){//当我们覆盖的区间的右端点+1>=当前找的区间的左端点时我们找覆盖最多的右端点
			int j=i;
			while(i<=last+mx[last]-1+1&&i
				if(i+mx[i]-1>j+mx[j]-1){
					j=i;
				}
				i++;
			}
			i=j;
			last=j;
		//	cout<
			flag++;
			ans.push_back({num[j],j+1}); 
			if(last+mx[last]-1>=n-1)break;
		}
	}
	if(last+mx[last]-1-1){//如果我们覆盖的区间的右端点小于我们要覆盖的区间说明不能覆盖满
		cout<<-1<
	}else {//否则输出
		cout<
		for(int i=0;isize() ;i++){
			cout<" "<
		}
	}
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t=1;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}
/*
1
bababa
2
ba
aba
*/