C++で文字列の一意のサブシーケンスの数をカウントするプログラム

文字列sがあるとすると、sの空でない一意のサブシーケンスの数を見つける必要があります。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します。

したがって、入力がs ="xxy"の場合、出力は5になります。これは、 "x"、 "xx"、 "xy"、 "y"、および"xxy"の5つのサブシーケンスがあるためです。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7

• n：=sのサイズ

• サイズ26の配列テーブルを定義する

• res：=0

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、do-

  • 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

• 解像度を返す

理解を深めるために、次の実装を見てみましょう-

例

#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