题目：

思路：

还能这样DP！？

题意简单：你有 n 个字符串 s，每次操作你可以选任意一个 s，如果 t 中有子串 s，那么你可以将这个 t 中这个子串染色，求将 t 全染色的最少操作次数

本题也是经典的贪心贪不明白，所以考虑DP

我们定义 f[i] 为将前 i 个字符全染色需要的最小操作数，那么转移直接暴力枚举每个字符串 s 即可，特别注意的就是，如果我们要染色的话，那么起点就是 j = i - s.length，考虑染最后一个位置即可知道，同时对于每个 f[k]，其中 k 为 j ~ i，我们要取最小值，因为我们是将这一段全染色了，但是其之前染色的操作可能并不是 f[j] 最小，我们只不过是以 j 为起点而已

我们还需要的就是知道具体操作，所以还需要记录操作，这个也很简单，我们记录每个点的父节点（即 i 是从谁转移来的）即可，具体还是看代码吧

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    string t;
    cin >> t;
    int n = t.size();
    t = ' ' + t;
    int k;
    cin >> k;
    vector<string> s(k+1);
    for (int i = 1; i <= k; i++)
    {
        cin >> s[i];
    }
    vector<int> f(n + 1, 114514), pre(n + 1, 0);
    f[0] = 0;
    vector<pair<int, int>> ans(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            int len = s[j].length();
            if (i >= len)
            {
                if (t.substr(i - len + 1, len) == s[j])
                {
                    for (int l = i - len; l < i; l++)
                    {
                        if(f[l] + 1 < f[i])
                        {
                            f[i] = f[l] + 1;
                            pre[i] = l;
                            ans[i] = {i - len + 1,j};
                        }
                    }
                }
            }
        }
    }
    if (f[n] == 114514)
        cout << "-1\n";
    else
    {
        cout << f[n] << endl;
        int now = n;
        while (now)
        {
            cout << ans[now].second << " " << ans[now].first << endl;
            now = pre[now];
        }
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}