Đếm số lần xuất hiện chuỗi con bằng đệ quy trong Java

Cho hai chuỗi str1 (chuỗi cha) và str2 (chuỗi con). Đếm số lần str2 xuất hiện trong str1 bằng phương pháp đệ quy.

Ví dụ

str1 = "TPisTPareTPamTP", str2 = "TP" → Kết quả: 4.

str1 = "HiHOwAReyouHiHi", str2 = "Hi" → Kết quả: 3.

Ý tưởng đệ quy

• Nếu str1 chứa str2: tìm vị trí đầu tiên, thay thế lần xuất hiện đầu tiên bằng chuỗi rỗng, gọi đệ quy với chuỗi mới + 1.
• Nếu không chứa: trả về 0.

Triển khai Java

public class RecursiveSubstringCount {
    public static int countOccurrences(String str, String sub) {
        if (str.contains(sub)) {
            // replaceFirst chỉ thay thế lần xuất hiện đầu tiên
            return 1 + countOccurrences(str.replaceFirst(sub, ""), sub);
        }
        return 0;
    }

    public static void main(String[] args) {
        String str1 = "TPisTPareTPamTP";
        String str2 = "TP";
        System.out.println("Số lần xuất hiện: " + countOccurrences(str1, str2)); // 4

        String s1 = "HiHOwAReyouHiHi";
        String s2 = "Hi";
        System.out.println("Số lần xuất hiện: " + countOccurrences(s1, s2)); // 3
    }
}

Phân tích

• Thời gian: O(n*m) trong trường hợp xấu (mỗi lần replaceFirst quét lại chuỗi).
• Không gian: O(n) do tạo chuỗi mới mỗi lần đệ quy + call stack.
• Lưu ý: Đệ quy có thể gây StackOverflowError nếu chuỗi rất dài và xuất hiện nhiều lần. Cách lặp (iterative) an toàn hơn cho production.

Cách lặp (khuyên dùng thực tế)

public static int countIterative(String str, String sub) {
    int count = 0, idx = 0;
    while ((idx = str.indexOf(sub, idx)) != -1) {
        count++;
        idx += sub.length(); // tránh đếm trùng lặp chồng chéo
    }
    return count;
}

Cách lặp O(n) time, O(1) space, không lo tràn stack.