数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 相同的数组 table，并用 0 填充
table[0] := 1
对于 i := 0，当 i < s 的长度，更新 (i 加 1)，执行：
定义一个数组 onsave := table
对于 j := 0，当 j < table 的长度，更新 (j 加 1)，执行：
如果 s[i] 等于 t[j]，则：
table[j + 1] = (table[j + 1] mod m + onsave[j] mod m)
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
更新于：2020年12月25日
89 次浏览
广告