โปรแกรม Java หาสับสตริง (Subsets/Substrings) ทั้งหมดของสตริง

การหาสับสตริง (Substrings) ทั้งหมดของสตริงใน Java

สับสตริง (Substring) คือลำดับตัวอักษรที่ต่อเนื่องกันภายในสตริง สำหรับสตริงยาว n จะมีสับสตริงทั้งหมด n(n+1)/2 ตัว (รวมสตริงว่างไม่รวม)

อัลกอริทึม (Nested Loops)

1. ลูปภายนอก: ดัชนีเริ่มต้น i (0 ถึง n-1)
2. ลูปภายใน: ดัชนีสิ้นสุด j (i ถึง n-1)
3. ดึงสับสตริงด้วย substring(i, j+1)
4. เก็บในอาร์เรย์หรือแสดงผลทันที

ตัวอย่างที่ 1: ใน main โดยตรง

public class Demo {
    public static void main(String[] args) {
        String inputString = "JVM";
        int length = inputString.length();
        int temp = 0;
        
        // จำนวนสับสตริง = n(n+1)/2 = 3*4/2 = 6
        String[] subStrings = new String[length * (length + 1) / 2];
        
        System.out.println("สตริงต้นฉบับ: " + inputString);
        
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                subStrings[temp] = inputString.substring(i, j + 1);
                temp++;
            }
        }
        
        System.out.println("สับสตริงทั้งหมด:");
        for (String s : subStrings) {
            System.out.println(s);
        }
    }
}

ผลลัพธ์

สตริงต้นฉบับ: JVM
สับสตริงทั้งหมด:
J
JV
JVM
V
VM
M

ตัวอย่างที่ 2: แบบ OOP (Encapsulation)

public class Demo {
    static void printAllSubstrings(String input) {
        int n = input.length();
        String[] subStrings = new String[n * (n + 1) / 2];
        int index = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                subStrings[index++] = input.substring(i, j + 1);
            }
        }
        
        System.out.println("สับสตริงทั้งหมดของ \"" + input + "\":");
        for (String s : subStrings) {
            System.out.print(s + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        printAllSubstrings("JVM");
        printAllSubstrings("ABC");
    }
}

วิธีที่ทันสมัยกว่า (Java 8+ Streams)

import java.util.stream.*;

public class ModernDemo {
    public static void main(String[] args) {
        String input = "JVM";
        
        // สร้างสับสตริงทั้งหมดด้วย Stream
        List substrings = IntStream.range(0, input.length())
            .boxed()
            .flatMap(i -> IntStream.rangeClosed(i + 1, input.length())
                .mapToObj(j -> input.substring(i, j)))
            .collect(Collectors.toList());
        
        System.out.println("สับสตริงของ " + input + ": " + substrings);
    }
}

ผลลัพธ์ Stream

สับสตริงของ JVM: [J, JV, JVM, V, VM, M]

ความซับซ้อน (Complexity)

• เวลา: O(n³) - substring() ใน Java เก่าสร้างสตริงใหม่ O(k), รวมเป็น O(n³)
• พื้นที่: O(n²) - เก็บสับสตริงทั้งหมด
• Java 7+: substring() ใช้ shared char array → O(n²) เวลา

การเพิ่มประสิทธิภาพ

// หากแค่ต้องการประมวลผล ไม่ต้องเก็บทั้งหมด
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
        String sub = input.substring(i, j);
        process(sub); // ประมวลผลทันที
    }
}

กรณีการใช้งาน

• String matching / Pattern searching
• DNA sequence analysis
• Text processing, NLP
• Palindrome detection