Giả sử chúng ta có hai xâu chữ thường s và t, chúng ta phải tìm số dãy con của s bằng t. Nếu câu trả lời là rất lớn thì trả về kết quả bằng 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là s ="abbd" t ="bd", thì đầu ra sẽ là 2, vì có thể có hai dãy con "bd".
-
s [1] nối s [3]
-
s [2] nối s [3].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
m:=10 ^ 9 + 7
-
nếu kích thước của t bằng 0, thì -
-
trả về 0
-
-
nếu t giống với s, thì -
-
trả lại 1
-
-
nếu kích thước của t> kích thước của s, thì -
-
trả về 0
-
-
Xác định một bảng mảng có kích thước giống như kích thước của t + 1 và điền bằng 0
-
bảng [0]:=1
-
để khởi tạo i:=0, khi i
-
Xác định một onsave mảng:=table
-
để khởi tạo j:=0, khi j
-
nếu s [i] giống với t [j] thì -
-
table [j + 1] =(table [j + 1] mod m + onsave [j] mod m)
-
-
-
-
table [j + 1] =(table [j + 1] mod m + onsave [j] mod m)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
"abbd", "bd"
Đầu ra
2