C++の反復法を使用して文字列のすべてのサブシーケンスを出力します

この問題では、文字列が与えられ、与えられた文字列から部分文字列を見つける必要があります。検出される部分文字列は、母音で始まり、定数文字で終わる必要があります。

文字列 文字の配列です。

この問題で生成される部分文字列は、文字列の一部の文字を削除することで生成できます。文字列の順序を変更せずに。

Input: ‘abc’
Output: ab, ac, abc

この問題を解決するために、文字列を繰り返して母音を修正し、次のシーケンスをチェックします。解決策を見つけるためのアルゴリズムを見てみましょう-

アルゴリズム

Step 1: Iterate of each character of the string, with variable i.
Step 2: If the ith character is a vowel.
Step 3: If the jth character is a consonant.
Step 4: Add to the HashSet, substring from 1st character to jth character.
Step 5: Repeat the following steps and find substrings from the string.

反復アプローチでは、すべての文字列を反復処理します。 1から2 ^{legth（string）} -1。

例

#include <bits/stdc++.h>
using namespace std;
string subString(string s, int binary){
   string sub = "";
   int pos;
   while(binary>0){
      pos=log2(binary&-binary)+1;
      sub=s[pos-1]+sub;
      binary= (binary & ~(1 << (pos-1)));
   }
   reverse(sub.begin(),sub.end());
   return sub;
}
void findAllSubStrings(string s){
   map<int, set<string> > sorted_subsequence;
   int len = s.size();
   int limit = pow(2, len);
   for (int i = 1; i <= limit - 1; i++) {
      string sub = subString(s, i);
      sorted_subsequence[sub.length()].insert(sub);
   }
   for (auto it : sorted_subsequence) {
      for (auto ii : it.second)
         cout<<ii<<" ";
      cout<<"\t";
   }
}
int main() {
   string s = "wxyz";
   cout<<"The substring are :\n";
   findAllSubStrings(s);
   return 0;
}

出力

サブストリングは-

w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz