資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：統計字串唯一子序列的個數
假設我們有一個字串s，我們需要找到s的非空唯一子序列的個數。如果答案非常大，則將結果模10^9 + 7。
因此，如果輸入類似於s = "xxy"，則輸出將為5，因為存在五個子序列：“x”，“xx”，“xy”，“y”和“xxy”。
為了解決這個問題，我們將遵循以下步驟：
m := 10^9 + 7
n := s的長度
定義一個大小為26的陣列table
res := 0
初始化 i := 1，當 i <= n 時，更新 (i增加1)，執行：
c := s[i − 1] - 'a' 的ASCII值
curr := (res + 1 − table[c] + m) mod m
res := (res + curr) mod m
table[c] := (table[c] + curr) mod m
返回 res
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
int n = s.size();
vector<int> table(26);
long long res = 0;
for (int i = 1; i <= n; ++i) {
int c = s[i − 1] − 'a';
int curr = (res + 1 − table[c] + m) % m;
res = (res + curr) % m;
table[c] = (table[c] + curr) % m;
}
return res;
}
int main(){
string s = "xxy";
cout << solve(s);
}輸入
"xxy"
輸出
5
更新於：2020-12-26
576 次瀏覽
廣告