Đếm xâu con khác nhau bắt đầu và kết thúc bằng chuỗi cho trước trong C++

Giới thiệu

Cho chuỗi str và hai chuỗi con start, end. Đếm số lượng xâu con khác nhau của str bắt đầu bằng start và kết thúc bằng end.

Ví dụ

str = "getmesomecoffee", start = "m", end = "e"

Các xâu con thỏa mãn:

1. me (vị trí 3-4)
2. mesome (3-8)
3. mesomemecoffe (3-14)
4. mesomemecoffee (3-15)
5. mecoffe (9-14)
6. mecoffee (9-15)

Kết quả: 6

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int getSubstringsCount(string str, string start, string end) {
    int n = str.length();
    int start_len = start.length();
    int end_len = end.length();
    
    // Đánh dấu vị trí bắt đầu/kết thúc khớp
    vector<bool> start_match(n, false), end_match(n, false);
    
    for (int i = 0; i <= n - start_len; i++) {
        if (str.substr(i, start_len) == start) {
            start_match[i] = true;
        }
    }
    for (int i = 0; i <= n - end_len; i++) {
        if (str.substr(i, end_len) == end) {
            end_match[i] = true;
        }
    }
    
    // Tìm tất cả xâu con hợp lệ
    set<string> substrings;
    
    for (int i = 0; i < n; i++) {
        if (!start_match[i]) continue;
        
        string current = "";
        for (int j = i; j < n; j++) {
            current += str[j];
            
            // Kiểm tra xem có kết thúc bằng end tại vị trí j không
            if (j <= n - end_len && end_match[j]) {
                // Xác nhận xâu con kết thúc đúng bằng end
                if (current.length() >= end_len && 
                    current.substr(current.length() - end_len) == end) {
                    substrings.insert(current);
                }
            }
        }
    }
    
    return substrings.size();
}

int main() {
    string str = "getmesomecoffee";
    string start = "m";
    string end = "e";
    cout << getSubstringsCount(str, start, end) << endl;
    return 0;
}

Kết quả chạy chương trình

6

Phân tích độ phức tạp

• Thời gian: O(n² × L) - n là độ dài str, L là độ dài xâu con trung bình (do substr và set)
• Không gian: O(n² × L) - lưu tất cả xâu con khác nhau

Tối ưu hóa: Sử dụng Trie hoặc Suffix Automaton

Để xử lý chuỗi lớn (n ~ 10⁵), cần cấu trúc dữ liệu nâng cao:

• Suffix Automaton: O(n) xây dựng, O(|start|+|end|) truy vấn
• Trie + DFS: Lưu các xâu con bắt đầu bằng start
• Rolling Hash: So sánh xâu con O(1), tổng O(n²) nhưng nhanh hơn thực tế

Lưu ý về code gốc

Code gốc có lỗi logic trong việc xây dựng xâu con (không xử lý đúng khi end_len > 1). Phiên bản trên đã sửa lỗi.

Kết luận

Bài toán tìm xâu con thỏa mãn điều kiện đầu/cuối, ứng dụng trong xử lý ngôn ngữ tự nhiên, tìm kiếm mẫu, bioinformatics.