In tất cả các chuỗi con của một chuỗi trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi và chúng ta phải in tất cả các dãy con của chuỗi. Chuỗi con được tạo ra được tạo bằng cách xóa các phần tử của chuỗi nhưng thứ tự vẫn giữ nguyên (tức là không thể thay đổi thứ tự).

Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -

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

Giải thích - Trong ví dụ trên, chúng ta có thể thấy các ký tự duy nhất bị xóa để tạo chuỗi con. Không, việc sắp xếp lại diễn ra.

Có thể có nhiều phương pháp để giải quyết vấn đề này, ở đây chúng ta sẽ thảo luận một vài phương pháp trong số đó để hiểu các phương pháp.

Một là bằng cách chọn các phần tử của chuỗi và loại bỏ một số ít để tạo thứ tự. Trong phương pháp này, chúng tôi sẽ chọn một vài phần tử và xóa phần còn lại để tạo chuỗi con.

Ví dụ

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

Đầu ra

Tất cả các chuỗi con được tìm thấy là -

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

Phương pháp khác có thể lặp qua chuỗi và tạo chuỗi con. Và bỏ các ký tự của dãy để tạo chuỗi con. Ở đây, chúng ta sẽ sử dụng một danh sách để lưu trữ các chuỗi con. Và kiểm tra xem trình tự tìm thấy đã được tìm thấy hay chưa.

Ví dụ

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

Đầu ra

Hệ số phụ là

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

Một phương pháp nữa có thể là sửa chữa các ký tự và tìm chuỗi con. Trong phương pháp này, chúng tôi sẽ sửa lần lượt các phần tử của chuỗi và sử dụng các ký tự cố định này, chúng tôi sẽ tìm ra dãy con. Việc gọi đệ quy của phương thức này tạo ra chuỗi con bắt buộc.

Ví dụ

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

Đầu ra

Các chuỗi con là -

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