สมมติว่าเรามีสตริงตัวพิมพ์เล็กสองตัว s และ t เราต้องหาจำนวนลำดับย่อยของ s ที่เท่ากับ t หากคำตอบมีขนาดใหญ่มาก ให้ส่งคืนผลลัพธ์ 10^9 + 7
ดังนั้น หากอินพุตเป็น s ="abbd" t ="bd" ผลลัพธ์จะเป็น 2 เนื่องจากมีความเป็นไปได้ที่ตามมาสองรายการ "bd"
-
s[1] ต่อกัน s[3]
-
s[2] ต่อ s[3].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9 + 7
-
ถ้าขนาดของ t เท่ากับ 0 แล้ว −
-
คืนค่า 0
-
-
ถ้า t เหมือนกับ s แล้ว −
-
กลับ 1
-
-
ถ้าขนาดของ t> ขนาดของ s แล้ว −
-
คืนค่า 0
-
-
กำหนดตารางอาร์เรย์ที่มีขนาดเท่ากับขนาด t + 1 และเติมด้วย 0
-
ตาราง[0] :=1
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
กำหนดอาร์เรย์ onsave :=ตาราง
-
สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของตาราง ให้อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ −
-
ถ้า s[i] เหมือนกับ t[j] แล้ว −
-
table[j + 1] =(ตาราง[j + 1] mod m + onsave[j] mod m)
-
-
-
-
table[j + 1] =(ตาราง[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
