C++の個別のサブシーケンスII

文字列Sがあるとすると、Sの個別のサブシーケンスの数をカウントする必要があります。結果は大きくなる可能性があるため、10 ^ 9+7を法とする答えを返します。

したがって、入力が「bab」のような場合、出力は6になります。これは、「a」、「b」、「ba」、「ab」、「bb」、「abb」の6つの異なるシーケンスがあるためです。

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

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod MOD）+（b mod MOD））mod MOD

• 関数sub（）を定義します。これには、a、b、

  が必要です。

• return（（（a mod MOD）-（b mod MOD））+ MOD）mod MOD

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod MOD）*（b mod MOD））mod MOD

• メインメソッドから、次のように-

• n：=sのサイズ

• サイズ26の配列dpを定義します

• res：=0

• s：=sの前にスペースを連結する

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

  • x：=s [i]

  • 追加：=sub（add（res、1）、dp [x-'a']）

  • dp [x-'a'] =add（dp [x-'a']、追加）

  • res：=add（res、added）

• 解像度を返す

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

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ( (a % MOD) + (b % MOD) ) % MOD;
   }
   lli sub(lli a, lli b){
      return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
   }
   lli mul(lli a, lli b){
      return ( (a % MOD) * (b % MOD) ) % MOD;
   }
   int distinctSubseqII(string s) {
      int n = s.size();
      vector <lli> dp(26);
      int res = 0;
      s = " " + s;
      for(lli i = 1; i <= n; i++){
         char x = s[i];
         int added = sub(add(res, 1) , dp[x - 'a']);
         dp[x - 'a'] = add(dp[x - 'a'], added);
         res = add(res, added);
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.distinctSubseqII("bab"));
}

入力

"bab"

出力

6