C++에서 문자열의 모든 하위 시퀀스 인쇄

이 문제에서는 문자열이 주어지고 문자열의 모든 하위 시퀀스를 인쇄해야 합니다. 생성된 하위 문자열은 문자열의 요소를 삭제하여 생성되지만 순서는 동일하게 유지됩니다(즉, 순서는 변경할 수 없음).

주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

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

설명 − 위의 예에서 부분 문자열을 생성하기 위해 삭제된 문자만 볼 수 있습니다. 아니요, 재정렬이 발생합니다.

이 문제를 해결하는 방법은 여러 가지가 있을 수 있습니다. 여기서는 방법을 이해하기 위해 그 중 몇 가지에 대해 설명하겠습니다.

하나는 문자열의 요소를 선택하고 일부를 제거하여 시퀀스를 만드는 것입니다. 이 방법에서는 몇 가지 요소를 선택하고 나머지를 삭제하여 하위 문자열을 만듭니다.

예시

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]

또 다른 방법은 문자를 수정하고 하위 문자열을 찾는 것입니다. 이 방법에서는 문자열의 요소를 하나씩 수정하고 이러한 고정된 문자를 사용하여 하위 시퀀스를 찾습니다. 이 메서드를 재귀적으로 호출하면 필요한 문자열 하위 시퀀스가 ​​생성됩니다.

예시

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);
   }
}

출력

하위 문자열은 -

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