题解 | 子串-NOIP2015提高组复赛

算法知识点: 线性DP，前缀和

复杂度：

解题思路：

状态表示：f[i, j, k]表示只用S的前i个字母，选取了k段，可以匹配T的前j个字母的方案数。

状态计算：将f[i, j, k]表示的所有方案分成两大类：

1. 不用S[i]，则方案数是f[i - 1, j, k]；
2. 使用S[i]，那么可以按S[i]所在的一段一共有多少字母继续分类：
   • 如果有t个字母，则方案数是f[i - t, j - t, k - 1]

所以f[i, j, k] = f[i - 1, j, k] + sum(f[i - t, j - t, k - 1])。
其中t只要满足S[i - t + 1] == T[j - t + 1]就可以一直往前枚举，因此最坏情况下的时间复杂度是 ，会超时。

接下来考虑如何优化。

我们发现f[i, j, k]第二项的表达式和f[i - 1, j - 1, k]第二项的表达式很像，具有递推关系，因此可以令sum[i, j, k] = sum(f[i - t, j - t, k])，则：

• 如果S[i] == T[j]，那么sum[i, j, k] = sum[i - 1, j - 1, k] + f[i - 1, j - 1, k - 1]；
• 如果S[i] != T[j]，那么sum[i, j, k] = 0；

至此，时间复杂度可以降至 。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 210;
 
int n, m, K;
char S[N], T[N];
int f[N][N], sum[N][N];
 
int main()
{
    scanf("%d%d%d", &n, &m, &K);
    scanf("%s%s", S + 1, T + 1);
 
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j; j--)
            for (int k = K; k; k--)
            {
                if (S[i] == T[j]) sum[j][k] = sum[j - 1][k] + f[j - 1][k - 1];
                f[j][k] += sum[j][k];
            }
 
    printf("%d\n", f[m][K]);
    return 0;
}