程序查找与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]modm+onsave[j]modm）
定义一个数组onsave：=table
对于初始化j：=0，当j<表的大小时，更新（将j增加1），执行-
table[j+1]=（table[j+1]modm+onsave[j]modm）
让我们看下面的实现以更好地理解-
示例
#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