程序查找与C ++中的目标相同的唯一子序列数

假设我们有两个小写的字符串s和t，我们必须找到s等于t的子序列数。如果答案很大，则返回结果10 ^ 9 + 7。

因此，如果输入类似于s =“ abbd” t =“ bd”，则输出将为2，因为存在两个可能的子序列“ bd”。

• s [1]连接s [3]

• s [2]连接s [3]。

为了解决这个问题，我们将遵循以下步骤-

• m：= 10 ^ 9 + 7

• 如果t的大小等于0，则-

• 返回0

• 如果t与s相同，则-

• 返回1

• 如果t的大小> s的大小，则-

• 返回0

• 定义大小与t + 1相同的数组表，并用0填充

• 桌子[0]：= 1

• 对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-

• 如果s [i]与t [j]相同，则-

• table [j + 1] =（table [j + 1] mod m + onsave [j] mod m）

• 定义一个数组onsave：= table

• 对于初始化j：= 0，当j <表的大小时，更新（将j增加1），执行-

• table [j + 1] =（table [j + 1] mod m + onsave [j] mod m）

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
   int m = 1000000007;
   if (t.size() == 0)
      return 0;
   if (t == s)
      return 1;
   if (t.size() > s.size())
      return 0;
   vector<int> table(t.size() + 1, 0);
   table[0] = 1;
   for (int i = 0; i < s.size(); i++) {
      vector<int> onsave = table;
      for (int j = 0; j < table.size(); j++) {
         if (s[i] == t[j]) {
            table[j + 1] = (table[j + 1] % m + onsave[j] % m) %m;
         }
      }
   }
   return table[t.size()] % m;
}
main(){
   string s = "abbd", t = "bd";
   cout << (solve(s, t));
}

输入值

"abbd", "bd"

2