এই সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া হয়েছে এবং আমাদের স্ট্রিংটির সমস্ত অনুবর্তনগুলি প্রিন্ট করতে হবে। তৈরি করা সাবস্ট্রিংটি স্ট্রিংয়ের উপাদানগুলি মুছে ফেলার মাধ্যমে তৈরি করা হয় কিন্তু ক্রম একই থাকে (অর্থাৎ অর্ডার পরিবর্তন করা যাবে না)।
বিষয়টি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
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
