数据结构
网络
关系数据库管理系统(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 次浏览
广告