Giả sử chúng ta có một chuỗi S, chúng ta phải đếm số lượng các dãy con khác biệt của S. Kết quả có thể lớn, vì vậy chúng ta sẽ trả về mô-đun câu trả lời là 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là "bab", thì đầu ra sẽ là 6, vì có 6 chuỗi khác nhau, đó là "a", "b," ba "," ab "," bb "," abb ".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm add (), điều này sẽ lấy a, b,
-
return ((a mod MOD) + (b mod MOD)) mod MOD
-
Xác định một hàm sub (), điều này sẽ lấy a, b,
-
return ((a mod MOD) - (b mod MOD)) + MOD) mod MOD
-
Xác định một hàm mul (), điều này sẽ nhận a, b,
-
return ((a mod MOD) * (b mod MOD)) mod MOD
-
Từ phương thức chính, như sau -
-
n:=kích thước của s
-
Xác định một mảng dp có kích thước 26
-
res:=0
-
s:=nối khoảng trắng trước s
-
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
-
x:=s [i]
-
đã thêm:=sub (thêm (res, 1), dp [x - 'a'])
-
dp [x - 'a'] =add (dp [x - 'a'], đã thêm)
-
res:=add (res, đã thêm)
-
-
trả lại res
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;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % MOD) + (b % MOD) ) % MOD;
}
lli sub(lli a, lli b){
return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
}
lli mul(lli a, lli b){
return ( (a % MOD) * (b % MOD) ) % MOD;
}
int distinctSubseqII(string s) {
int n = s.size();
vector <lli> dp(26);
int res = 0;
s = " " + s;
for(lli i = 1; i <= n; i++){
char x = s[i];
int added = sub(add(res, 1) , dp[x - 'a']);
dp[x - 'a'] = add(dp[x - 'a'], added);
res = add(res, added);
}
return res;
}
};
main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
} Đầu vào
"bab"
Đầu ra
6