文字列のすべてのサブシーケンスをC++で出力します

この問題では、文字列が与えられ、文字列のすべてのサブシーケンスを出力する必要があります。生成される部分文字列は、文字列の要素を削除することによって作成されますが、順序は同じままです（つまり、順序を変更することはできません）。

トピックをよりよく理解するために例を見てみましょう-

Input: xyz
Output: x,y,z,xy,yz,xz,xyz

説明 −上記の例では、サブストリングを作成するために文字のみが削除されていることがわかります。いいえ、再配置が行われます。

この問題を解決するには複数の方法があります。ここでは、方法を理解するためにそれらのいくつかについて説明します。

1つは、文字列の要素を選択し、いくつかを削除してシーケンスを作成することです。この方法では、いくつかの要素を選択し、残りを削除して部分文字列を作成します。

例

import java.util.*;
class Main{
   public static ArrayList<String>subStringSeq=new ArrayList<String>();
   public static void main(String[] args) {
      String s="pqrs";
      System.out.println("All the substring found are :");
      findSubString(s,"");
      System.out.println(subStringSeq);
   }
   public static void findSubString(String s, String ans) {
      if(s.length()==0){
         subStringSeq.add(ans);
         return;
      }
      findSubString(s.substring(1),ans+s.charAt(0)) ;
      findSubString(s.substring(1),ans);
   }
}

出力

見つかったすべての部分文字列は-

[pqrs, pqr, pqs, pq, prs, pr, ps, p, qrs, qr, qs, q, rs, r, s, ]

別の方法 文字列を反復処理してサブ文字列を生成する可能性があります。そして、シーケンスの文字を削除してサブストリングを生成します。ここでは、リストを使用して部分文字列を格納します。そして、見つかったシーケンスがすでに見つかっているかどうかを確認します。

例

import java.util.HashSet;
public class Main{
   static HashSet<String> subString = new HashSet<>();
   static void findSubString(String str){
      for (int i = 0; i < str.length(); i++) {
         for (int j = str.length(); j > i; j--) {
            String sub_str = str.substring(i, j);
            if (!subString.contains(sub_str))
               subString.add(sub_str);
            for (int k = 1; k < sub_str.length() - 1; k++) {
               StringBuffer sb = new StringBuffer(sub_str);
               sb.deleteCharAt(k);
               if (!subString.contains(sb));
                  findSubString(sb.toString());
            }
         }
      }
   }
   public static void main(String[] args){
      String s = "pqrs";
      System.out.println("The subsequence is ");
      findSubString(s);
      System.out.println(subString);
   }
}

出力

サブシーケンスは

[rs, pq, qr, pr, qs, ps, prs, p, pqr, q, r, s, pqs, qrs, pqrs]

もう1つの方法は、文字を修正して部分文字列を見つけることです。このメソッドでは、文字列の要素を1つずつ修正し、これらの固定文字を使用して、サブシーケンスを見つけます。このメソッドを再帰的に呼び出すと、必要な文字列サブシーケンスが作成されます。

例

class Main {
   static void subString(String str, int n,
   int index, String curr){
      if (index == n){
         return;
      }
      System.out.print(curr + ", ");
      for (int i = index + 1; i < n; i++){
         curr += str.charAt(i);
         subString(str, n, i, curr);
         curr = curr.substring(0, curr.length() - 1);
      }
   }
   static void printSubStrings(String str){
      int index = -1;
      String curr = "";
      subString(str, str.length(), index, curr);
   }
   public static void main(String[] args){
      String str = "pqrs";
      System.out.println("The subStrings are :") ;
      printSubStrings(str);
   }
}

出力

subStringsは-

p, pq, pqr, pqrs, pqs, pr, prs, ps, q, qr, qrs, qs, r, rs, s