資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告