程序计算C ++中字符串的唯一子序列数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串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）mod m

    • res：=（res + curr）mod m

    • table [c]：=（table [c] + curr）mod m

  • 返回资源

让我们看下面的实现以更好地理解-

示例

#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

以上是 程序计算C ++中字符串的唯一子序列数 的全部内容， 来源链接： utcz.com/z/321460.html

回到顶部