程序计算C ++中字符串的唯一子序列数
假设我们有一个字符串s，我们必须找到s的非空唯一子序列数。如果答案很大，则将结果修改为10^9+7。
因此，如果输入类似于s=“xxy”，则输出将为5，因为有五个子序列：“x”，“xx”，“xy”，“y”和“xxy”。
为了解决这个问题，我们将遵循以下步骤-
m：=10^9+7
n：=s的大小
定义大小为26的数组表
res：=0
对于初始化i：=1，当i<=n时，更新（将i增加1），-
c：=s[i-1]-ASCII'a'
curr：=（res+1-table[c]+m）modm
res：=（res+curr）modm
table[c]：=（table[c]+curr）modm
返回资源
让我们看下面的实现以更好地理解-
示例
#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
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短