程序查找与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