程序计算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