C++の2つの文字列で共通のサブシーケンスをカウントします

2つの文字列が与えられます。たとえば、文字を含むstr1とstr2があり、タスクは両方の文字列の共通のサブシーケンスを計算することです。以下のプログラムでは、動的計画法を使用しています。そのためには、動的計画法とは何か、どのような問題で使用できるかを知る必要があります。

動的計画法のアプローチは、分割統治法に似ており、問題をより小さく、さらにはより小さな可能なサブ問題に分解します。しかし、分割統治とは異なり、これらのサブ問題は独立して解決されません。むしろ、これらの小さなサブ問題の結果は記憶され、類似または重複するサブ問題に使用されます。

動的計画法は、問題が発生した場合に使用されます。問題は、同様のサブ問題に分割して、結果を再利用できるようにすることができます。ほとんどの場合、これらのアルゴリズムは最適化に使用されます。手元のサブ問題を解決する前に、動的アルゴリズムは以前に解決されたサブ問題の結果を調べようとします。最良の解決策を達成するために、サブ問題の解決策が組み合わされます。

つまり、-

Input − string str1 = “abc”
      String str2 = “ab”
Output − count is 3

説明 −指定された文字列から形成される一般的なサブシーケンスは次のとおりです：{‘a’、‘b’、‘ab’}。

Input − string str1 = “ajblqcpdz”
      String str2 = “aefcnbtdi”
Output − count is 11

一般的なサブシーケンスは −指定された文字列から形成される一般的なサブシーケンスは次のとおりです。{「a」、「b」、「c」、「d」、「ab」、「bd」、「ad」、「ac」、「cd」、「abd」 、「acd」}

以下のプログラムで使用されているアプローチは次のとおりです

• 2つの文字列、たとえばstr1とstr2を入力します。

• 文字列の文字数に応じて整数値を返すlength（）関数を使用して、指定された文字列の長さを計算し、str1の場合はlen1に、str2の場合はlen2に格納します。

• 動的計画法を実装するための2次元配列を作成します。たとえば、arr [len1 + 1] [len2 + 1]

• iがlen1未満になるまでiから0までのループを開始します

• ループ内で、jがlen2未満になるまでjから0までの別のループを開始します

• ループ内で、IF str1 [i-1] =str2 [j-1]を確認してから、arr [i] [j] =1 + arr [i] [j-1] + arr [i-1][j]<に設定します。 / P>

• それ以外の場合は、arr [i] [j] =arr [i] [j-1] + arr [i-1] [j] =arr [i-1] [j-1]

  に設定します。

• arr [len1] [len2]

  に戻る

• 結果を印刷します。

例

#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
   int n1 = str.length();
   int n2 = str2.length();
   int dp[n1+1][n2+1];
   for (int i = 0; i <= n1; i++){
      for (int j = 0; j <= n2; j++){
         dp[i][j] = 0;
      }
   }
   // for each character of str
   for (int i = 1; i <= n1; i++){
      // for each character in str2
      for (int j = 1; j <= n2; j++){
         // if character are same in both
         // the string
         if (str[i - 1] == str2[j - 1]){
            dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
         }
         else{
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
         }
      }
   }
   return dp[n1][n2];
}
int main(){
   string str = "abcdejkil";
   string str2 = "bcdfkaoenlp";
   cout <<"count is: "<<countsequences(str, str2) << endl;
   return 0;
}

例

上記のコードを実行すると、次の出力が得られます-

count is: 51