Bộ phân tích thực thể HTML (HTML Entity Parser) trong C++

Thiết kế bộ phân tích thay thế các thực thể HTML đặc biệt bằng ký tự tương ứng: "→", '→', &→&, >→>, <→<, ⁄→/. Các thực thể không hợp lệ giữ nguyên.

Ví dụ

Đầu vào: "& is changed but &ambassador; is not."
Đầu ra: "& is changed but &ambassador; is not."

Thuật toán quét chuỗi

1. Duyệt chuỗi, khi gặp & → đọc đến ; hoặc hết chuỗi.
2. Trích xuất token &...;, tra map thực thể hợp lệ.
3. Nếu có trong map → thay bằng ký tự, ngược lại giữ nguyên token.
4. Ký tự thường: thêm trực tiếp vào kết quả.

Triển khai C++

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

class Solution {
public:
    string entityParser(string text) {
        unordered_map mp = {
            {""", "\""}, {"'", "'"}, {"&", "&"},
            {">", ">"}, {"<", "<"}, {"⁄", "/"}
        };
        string res;
        for (int i = 0; i < text.size(); ) {
            if (text[i] == '&') {
                int j = i;
                while (j < text.size() && text[j] != ';') ++j;
                if (j < text.size()) {
                    string ent = text.substr(i, j - i + 1);
                    if (mp.count(ent)) res += mp[ent];
                    else res += ent;
                    i = j + 1;
                } else {
                    res += text[i++];
                }
            } else {
                res += text[i++];
            }
        }
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt chuỗi một lần.
• Không gian: O(N) kết quả + O(1) map.

Kết quả kiểm thử

Đầu vào: "& is changed but &ambassador; is not."
Đầu ra: & is changed but &ambassador; is not.