Giả sử ta có hai chuỗi chữ thường s và t, ta phải tìm số dãy con của s bằng t. Nếu kết quả quá lớn, trả về modulo 10^9 + 7.
Ví dụ: s = "abbd", t = "bd", đầu ra = 2, vì có hai dãy con "bd": s[1]+s[3] và s[2]+s[3].
Để giải quyết, ta làm theo các bước:
- m := 10^9 + 7.
- Nếu độ dài t == 0, trả 0.
- Nếu t == s, trả 1.
- Nếu độ dài t > độ dài s, trả 0.
- Định nghĩa mảng table kích thước độ dài t + 1, điền 0.
- table[0] := 1.
- for i := 0; i < độ dài s; ++i:
- Định nghĩa mảng onsave = table.
- for j := 0; j < table.size(); ++j:
- Nếu s[i] == t[j]: table[j+1] = (table[j+1] % m + onsave[j] % m) % m.
- Trả về table[t.size()] % m.
Xem triển khai dưới đây:
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