题目描述

难度:[绿]普及+/提高

输入$n(1≤n≤1000)$，$m$，$k(1≤k≤m≤200)$和长为$n$的字符串$s$，长为$m$的字符串$t$，只包含小写英文字母。

你需要从$s$中取出$k$个互不重叠的非空连续子串，然后把这$k$个子串按照其在$s$中的出现顺序依次连接起来，得到一个新的字符串。

输出有多少种方案可以使得这个新串与$t$相等。结果可能很大，模$10^9+7$后再输出。

注意：子串相同但取出的位置不同，也认为是不同的方案。

输入样例$1$

6 3 1 
aabaab 
aab

输出样例$1$

1

输入样例$2$

6 3 2 
aabaab 
aab

输出样例$2$

7

输入样例$3$

6 3 3 
aabaab 
aab

输出样例$3$

7

算法

动态规划

状态定义

$dp[i][j][rest]$表示已经从$s$的前缀$[1,i)$中选择出了$rest$个子段，拼出了$t$的前缀$[1,j)$。从$i$和$j$位置继续往后考虑，能够拼出$t$后缀$[j,m]$的方案数。很显然，答案应该是$dp[1][1][k]$。

状态转移

对于给定的$i$、$j$、$rest$：

1. 可以不选择$s[i]$，直接利用$s$的后缀$[i+1,n]$来拼凑$t$的后缀$[j,m]$。此时状态转移方程为$dp[i][j][k]=dp[i+1][j][rest]$。
2. 还可以选出一段$s[i…i+offset]$满足$s[i…i+offset]=t[j…j+offset]$，此时状态转移方程为$dp[i][j][rest]=\Sigma_{offset}dp[i+offset+1][j+offset+1][rest-1]$，其中$offset$表示所有满足$s[i…i+offset]=t[j…j+offset]$的偏移量，可以通过预处理得到。

后缀和优化

当$j=m+1$时，如果$rest=0$，就形成了一种合法的方案。但此时我们发现状态数量为$O(nm^2)$，而状态转移也是$O(m)$级别，因此时间复杂度为$O(nm^3)$，这也就意味着不能用记忆化搜索的方式来实现这个DP。根据情况$2$的状态转移基本可以确定需要用到后缀和的一个优化，在进行状态转移时维护$dp[i][j][rest]$斜线方向上的后缀和$sufsum[i][j][rest]=\Sigma_{x \in [0,min(n-i,m-j)]}dp[i+x][j+x][rest]$就可以让情况$2$中的状态转移在时间复杂度$O(1)$下完成。

滚动数组优化

有了后缀和的优化，时间复杂度基本就已经符合要求了。但本题还有个比较痛苦的点就是空间复杂度，如果开两个$O(nm^2)$的数组，会直接MLE。而我们发现状态转移方程中，$rest$层的状态仅由$rest-1$层的状态决定，所以可以用滚动数组优化掉$rest$那一维，这样就能把空间复杂度降低至$O(nm)$。

复杂度分析

时间复杂度

枚举预处理出$offset$的时间复杂度为$O(nm^2)$。状态数量为$O(nm^2)$，后缀和优化后状态转移是$O(1)$的，因此动态规划的时间复杂度为$O(nm^2)$。算法整体的时间复杂度为$O(nm^2)$。

空间复杂度

$offset$数组的空间复杂度为$O(nm)$，而利用滚动数组优化$sufsum$和$dp$数组之后，空间复杂度为$O(nm)$。因此，整个算法的额外空间复杂度为$O(nm)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010, M = 210, MOD = 1e9 + 7;
int n, m, k, mp[N][M], sufsum[2][N][M], dp[2][N][M];
char s[N], t[M];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    memset(mp, -1, sizeof mp);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int offset = 0;
            while(i + offset <= n && j + offset <= m && s[i + offset] == t[j + offset]) {
                mp[i][j] = offset++;
            }
        }
    }
    for(int i = m + 1; i <= n + 1; i++) {
        dp[0][i][m + 1] = 1;
        sufsum[0][i][m + 1] = 1;
    }
    for(int i = n; i >= 0; i--) {
        for(int j = m; j >= 0; j--) {
            sufsum[0][i][j] = (sufsum[0][i][j] + sufsum[0][i + 1][j + 1]) % MOD;
        }
    }
    for(int rest = 1; rest <= k; rest++) {
        if(rest == 2) {
            memset(sufsum[0], 0, sizeof(sufsum[0]));
        }
        int r = rest&1;
        for(int i = n; i >= 1; i--) {
            for(int j = m; j >= 1; j--) {
                int offset = mp[i][j];
                dp[r][i][j] = (dp[r][i + 1][j] + (sufsum[1 - r][i + 1][j + 1] - sufsum[1 - r][i + offset + 2][j + offset + 2] + MOD) % MOD) % MOD;
                sufsum[r][i][j] = (dp[r][i][j] + sufsum[r][i + 1][j + 1]) % MOD;
            }
        }
    }
    printf("%d\n", dp[k&1][1][1]);
    return 0;
}