Kiểm tra chuỗi theo mẫu aⁿbⁿ (anbn pattern) trong C++

Cho chuỗi chỉ chứa ký tự 'a' và 'b'. Kiểm tra xem chuỗi có dạng aⁿbⁿ hay không (tức là n ký tự 'a' liên tiếp theo sau bởi đúng n ký tự 'b' liên tiếp).

Ví dụ

• "aaabbb" -> True (n=3)
• "aabbb" -> False (số lượng không bằng)
• "aba" -> False (xen kẽ)
• "" (rỗng) -> True (n=0)

Phương pháp giải

1. Đếm số ký tự 'a' liên tiếp từ đầu chuỗi (gọi là countA). Dừng khi gặp ký tự khác 'a' hoặc hết chuỗi.
2. Kiểm tra độ dài chuỗi có bằng 2 * countA không. Nếu không -> False.
3. Kiểm tra phần còn lại của chuỗi (từ vị trí countA) có toàn ký tự 'b' không.

Chương trình C++

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

bool isAnBnPattern(const string& s) {
    int n = s.length();
    int i = 0;
    
    // 1. Đếm 'a' ở đầu
    while (i < n && s[i] == 'a') i++;
    int countA = i;
    
    // 2. Kiểm tra độ dài tổng
    if (2 * countA != n) return false;
    
    // 3. Kiểm tra phần còn lại toàn 'b'
    while (i < n) {
        if (s[i] != 'b') return false;
        i++;
    }
    return true;
}

int main() {
    vector<string> tests = {"aaaaaaaaaaaabbbbbbbbbbbb", "aabbb", "ab", "", "aaabbb", "aaaabbb"};
    for (auto &t : tests) {
        cout << "\"" << t << "\" -> " << (isAnBnPattern(t) ? "True" : "False") << endl;
    }
    return 0;
}

Đầu ra

"aaaaaaaaaaaabbbbbbbbbbbb" -> True
"aabbb" -> False
"ab" -> True
"" -> True
"aaabbb" -> True
"aaaabbb" -> False

Liên quan: Đây là bài toán kinh điển của **Ngôn ngữ bối cảnh tự do (Context-Free Language)**. Grammar: S -> aSb | ε. Không thể nhận diện bằng Biểu thức chính quy (Regular Expression) thuần túy (cần stack/đệ quy).