【ACWing】3713. 不同的子序列

https://www.acwing.com/problem/content/description/3716/

给定一个字符串 S S S和一个字符串 T T T，请问共有多少个 S S S的不同的子序列等于 T T T。

输入格式：
第一行包含整数 Q Q Q，表示共有 Q Q Q组测试数据。每组数据第一行包含字符串 S S S，第二行包含字符串 T T T。

输出格式：
每组数据输出一行，一个结果，由于结果可能很大，因此输出其对 1000000007 1000000007 1000000007取模后的值。

数据范围：
1 ≤ Q ≤ 50 1≤Q≤50 1≤Q≤50
1 ≤ ∣ S ∣ , ∣ T ∣ ≤ 1 0 4 1≤|S|,|T|≤10^4 1≤∣S∣,∣T∣≤104
保证 T 中的每个字符都是随机生成的。字符串中只包含小写字母。

可以用动态规划。设 f [ i ] [ j ] f[i][j] f[i][j]是 T T T的长 i i i的前缀在 S S S的长 j j j的前缀中作为子序列出现了多少次，长 0 0 0前缀指的是空串。那么有 ∀ j , f [ 0 ] [ j ] = 1 forall j, f[0][j]=1 ∀j,f[0][j]=1。考虑一般情形 f [ i ] [ j ] , i ≥ 1 f[i][j],ige 1 f[i][j],i≥1，首先不考虑 S S S的第 j j j个字符的话，出现次数是 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]；如果 T T T的第 i i i个字符等于 S S S的第 j j j个字符，那么取这两个字符匹配的情形又有 f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i−1][j−1]次，此时 f [ i ] [ j ] = f [ i ] [ j − 1 ] + f [ i − 1 ] [ j − 1 ] f[i][j]=f[i][j-1]+f[i-1][j-1] f[i][j]=f[i][j−1]+f[i−1][j−1]。可以考虑两个优化：
1、空间优化，可以用滚动数组；
2、外层遍历 i i i，内层遍历 j j j，如果发现对于某个 i i i，有 f [ i ] [ n ] = 0 f[i][n]=0 f[i][n]=0，那么说明不存在，直接可以输出 0 0 0。这个优化非常重要，能提前排除不存在的情形。

代码如下：

#include 
#include 
using namespace std;

const int N = 1e4 + 10, mod = 1e9 + 7;
int Q;
char s[N], t[N];
int f[2][N];

int main() {
  scanf("%dn", &Q);
  while (Q--) {
    scanf("%s", s);
    scanf("%s", t);
    int n = strlen(s), m = strlen(t);
    if (n < m) {
      puts("0");
      continue;
    }

    memset(f, 0, sizeof f);
    for (int j = 0; j <= n; j++) f[0][j] = 1;
    int i;
    for (i = 1; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        f[i & 1][j] = f[i & 1][j - 1];
        if (s[j - 1] == t[i - 1])
          f[i & 1][j] = (f[i & 1][j] + f[i - 1 & 1][j - 1]) % mod;
      }
      
      if (!f[i & 1][n]) break;
    }

	// 看是不是提前退出来的，如果是，说明不存在
    if (i <= m) puts("0");
    else printf("%dn", f[m & 1][n]);
  }
}

时间复杂度 O ( m n ) O(mn) O(mn)，空间 O ( n ) O(n) O(n)。