T2-19 字符串大师

题意理解

求有多少对 $(x, y)$，其中 $x$ 是 $S$ 的子串（连续），$y$ 是 $T$ 的子序列（不连续），且 $x$ 和 $y$ 内容相同。不同位置的子串/子序列视为不同。

---

思路分析

设 $dp[i][j]$ 表示：$S$ 的以第 $i$ 个字符结尾的所有子串，与 $T$ 的前 $j$ 个字符中的子序列匹配的总方案数。

即 $dp[i][j] = \sum_{l=1}^{i}$ （$T$ 前 $j$ 个字符中等于 $S[l..i]$ 的子序列数量）

状态转移：

考虑是否使用 $T[j]$：

1. 不使用 $T[j]$：$dp[i][j-1]$
2. 使用 $T[j]$（需要 $T[j] = S[i]$）：
   • 子串长度为 1：贡献 $1$（空子序列 + $T[j]$）
   • 子串长度 $> 1$：需要 $T$ 前 $j-1$ 个字符中匹配 $S[l..i-1]$ 的方案数，即 $dp[i-1][j-1]$

$$dp[i][j] = dp[i][j-1] + (T[j] = S[i] \text{ ? } dp[i-1][j-1] + 1 : 0)$$

边界条件：

• $dp[0][j] = 0$，$dp[i][0] = 0$

答案： $\\sum_{i=1}^{n} dp[i][m]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;  // 模数
const int MAXN = 5005;    // 最大字符串长度

char S[MAXN], T[MAXN];    // 两个字符串
long long dp[MAXN][MAXN]; // dp[i][j]表示S以第i个字符结尾的所有子串与T前j个字符匹配的方案数

int main() {
    cin >> S + 1 >> T + 1;  // 下标从1开始读入
    
    int n = strlen(S + 1), m = strlen(T + 1);  // 获取长度
    
    long long ans = 0;  // 答案
    
    for (int i = 1; i <= n; i++) {  // 枚举S的结尾位置
        for (int j = 1; j <= m; j++) {  // 枚举T的前j个字符
            dp[i][j] = dp[i][j - 1];  // 不使用T[j]
            if (T[j] == S[i]) {  // 使用T[j]匹配S[i]
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + 1) % MOD;  // 加上扩展的方案
            }
        }
        ans = (ans + dp[i][m]) % MOD;  // 累加以S[i]结尾的所有子串的答案
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}