C++のターゲットと同じ一意のサブシーケンスの数を見つけるプログラム

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

したがって、入力がs ="abbd" t ="bd"のようである場合、2つの可能なサブシーケンス "bd"があるため、出力は2になります。

• s[1]連結s[3]

• s[2]はs[3]を連結します。

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

• m：=10 ^ 9 + 7

• tのサイズが0と同じ場合、-

  • 0を返す

• tがsと同じ場合、-

  • 1を返す

• tのサイズ>sのサイズの場合、-

  • 0を返す

• t + 1のサイズと同じサイズの配列テーブルを定義し、0を入力します

• table [0]：=1

• 初期化i：=0の場合、i

  • 配列の保存を定義します：=テーブル

  • 初期化j：=0の場合、j <テーブルのサイズの場合、更新（jを1増やします）、実行-

    • s[i]がt[j]と同じ場合、-

      • table [j + 1] =（table [j + 1] mod m + onsave [j] mod m）

• table [j + 1] =（table [j + 1] mod m + onsave [j] mod m）

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

例

#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
   int m = 1000000007;
   if (t.size() == 0)
      return 0;
   if (t == s)
      return 1;
   if (t.size() > s.size())
      return 0;
   vector<int> table(t.size() + 1, 0);
   table[0] = 1;
   for (int i = 0; i < s.size(); i++) {
      vector<int> onsave = table;
      for (int j = 0; j < table.size(); j++) {
         if (s[i] == t[j]) {
            table[j + 1] = (table[j + 1] % m + onsave[j] % m) %m;
         }
      }
   }
   return table[t.size()] % m;
}
main(){
   string s = "abbd", t = "bd";
   cout << (solve(s, t));
}

入力

"abbd", "bd"

出力

2