题目描述

难度分:$1600$

输入$T(\leq 100)$表示$T$组数据。对于每组数据：

输入长度$\leq 100$的字符串$t$，只包含小写英文字母。然后输入$n(1≤n≤10)$和长为$n$的字符串数组$a$，每个$a[i]$的长度都$\leq 10$，只包含小写英文字母。

一开始$t$的每个字母都是黑色。每次操作，你可以选择一个$a[i]$，然后把$t$中的一个等于$a[i]$的子串染成红色。你需要把整个$t$染成红色。$t$中的同一个字母可以重复染色。

如果无法做到，输出$-1$。否则输出最小操作次数$k$，以及具体方案：

输出$k$行，每行两个数，分别表示每次操作选择的$i$，以及$t$中要染色的子串首字母的下标（从$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

输出样例

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

算法

记忆化搜索

思路很简单，和$LeetCode$那道“贴纸拼词”很像，感觉好像还更简单一点。这个数据规模一看就会从暴搜入手，进一步转化为记忆化搜索。先做预处理，预处理出一个二维数组$pos$，长度是字符串$t$的规模，$pos[index]$表示$t[index]$能够匹配字符串数组$a$中的哪些字符串，这个过程可以用$kmp$算法，但是本题的串都比较短，直接暴力匹配写得更快。

状态定义

$dp[i]$表示要匹配后缀$t[i…]$所需要的最少操作数，在这个定义下，答案就应该是$dp[0]$。

状态转移

对于当前位置$i$，遍历$pos[i]$，看这个位置能够与$a$中哪些字符串匹配。如果可以和$a[j]$匹配，那匹配完$i$后下一步要匹配的位置就可以是$[i+1,i+a[j].size()]$。状态转移方程为：

$dp[i]=min_{j \in pos[i],k \in [i+1,a[j].size()]}dp[k] + 1$

DP完成后，带着最少操作数$step=dp[0]$，再进行一次DFS，根据每一步最优解的转移来源倒推出方案就可以了。

复杂度分析

时间复杂度

预处理需要遍历$t$串的每个位置，假设$t$串的长度为$m$，对于它的每个位置，都需要检查它与$i \in [0,n)$的哪个$a[i]$是匹配的，暴力匹配的时间复杂度为$O(n)$，因此整个预处理过程的时间复杂度就是$O(mn^2)$。

接下来进行DP，状态数量为$O(m)$，单次转移需要遍历$pos[i]$（时间复杂度$O(n)$），和下一步可能的位置（时间复杂度$O(n)$），所以单次转移的时间复杂度为$O(n^2)$。DP整体的时间复杂度为$O(mn^2)$。

综上，整个算法的时间复杂度为$O(mn^2)$。

空间复杂度

$pos$数组长度为$m$，但是每个位置在最差情况下可以和$a$数组中所有字符串都匹配上，所以空间复杂度为$O(mn)$。DP数组$dp$的规模是$O(m)$的，只有$O(m)$级别的状态数量。因此，整个算法的额外空间复杂度为$O(mn)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 110, INF = 0x3f3f3f3f;
int T, n, f[N];
vector<int> pos[N];

void solve(string t, vector<string> strs) {
    int m = t.size();
    // 预处理
    memset(f, -1, sizeof f);
    for(int i = 0; i <= m; i++) {
        pos[i].clear();
    }
    function<bool(int, int)> equals = [&](int i, int index) {
        int len = strs[index].size();
        for(int j = 0; j < len; j++) {
            if(t[i + j] != strs[index][j]) return false;
        }
        return true;
    };
    for(int i = 0; i < n; i++) {
        int len = strs[i].size();
        for(int left = 0; left + len - 1 < m; left++) {
            if(equals(left, i)) {
                pos[left].push_back(i);     // t[left]开始可以匹配完strs[i]
            }
        }
    }
    // 记忆化搜索
    function<int(int)> dfs = [&](int index) {
        if(index >= m) return f[index] = 0;
        if(f[index] != -1) return f[index];
        int res = INF;
        for(int id: pos[index]) {
            int offset = strs[id].size();
            for(int j = 1; j <= offset; j++) {
                res = min(res, 1 + dfs(index + j));
            }
        }
        return f[index] = res;
    };
    int step = dfs(0);
    if(step == INF) {
        puts("-1");
        return;
    }
    printf("%d\n", step);
    // 还原方案
    vector<PII> ans;
    function<void(int, int)> dfs2 = [&](int index, int rest) {
        if(index >= m) return;
        bool flag = false;
        for(int id: pos[index]) {
            int offset = strs[id].size();
            for(int j = 1; j <= offset; j++) {
                if(f[index + j] + 1 == rest) {
                    ans.push_back({id + 1, index + 1});
                    dfs2(index + j, rest - 1);
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
    };
    dfs2(0, step);
    for(auto&pir: ans) {
        printf("%d %d\n", pir.first, pir.second);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        string t;
        cin >> t;
        vector<string> strs;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            string s;
            cin >> s;
            strs.push_back(s);
        }
        solve(t, strs);
    }
    return 0;
}