<p><strong>HTML entity parser</strong> is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.</p>

<p>The special characters and their entities for HTML are:</p>

<ul>
	<li><strong>Quotation Mark:</strong> the entity is <code>&amp;quot;</code> and symbol character is <code>&quot;</code>.</li>
	<li><strong>Single Quote Mark:</strong> the entity is <code>&amp;apos;</code> and symbol character is <code>&#39;</code>.</li>
	<li><strong>Ampersand:</strong> the entity is <code>&amp;amp;</code> and symbol character is <code>&amp;</code>.</li>
	<li><strong>Greater Than Sign:</strong> the entity is <code>&amp;gt;</code> and symbol character is <code>&gt;</code>.</li>
	<li><strong>Less Than Sign:</strong> the entity is <code>&amp;lt;</code> and symbol character is <code>&lt;</code>.</li>
	<li><strong>Slash:</strong> the entity is <code>&amp;frasl;</code> and symbol character is <code>/</code>.</li>
</ul>

<p>Given the input <code>text</code> string to the HTML parser, you have to implement the entity parser.</p>

<p>Return <em>the text after replacing the entities by the special characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;&amp;amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Output:</strong> &quot;&amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Explanation:</strong> The parser will replace the &amp;amp; entity by &amp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;and I quote: &amp;quot;...&amp;quot;&quot;
<strong>Output:</strong> &quot;and I quote: \&quot;...\&quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 10<sup>5</sup></code></li>
	<li>The string may contain any possible characters out of all the 256 ASCII characters.</li>
</ul>

class Solution {
    enum Token {
        QUOT = 0,
        APOS = 1,
        AMP = 2,
        GT = 3,
        LT = 4,
        FRASL = 5,
        UNKNOWN = 6,
        NUM_TOKENS = 7
    };

    string entity_map[NUM_TOKENS] = {
        "quot;", "pos;", "mp;", "gt;", "lt;", "frasl;", ""
    };

    char token_map[NUM_TOKENS] = {
        '"', '\'', '&', '>', '<', '/', '&',
    };

    Token parsePossibleEntity(const string &text, int &pos) {
        auto findSubstring = [](const string &s, int i, const string &t) {
            if (i + t.size() > s.size()) return false;
            return s.compare(i, t.size(), t) == 0;
        };

        if (pos + 3 > text.size()) return UNKNOWN;
        switch (text[pos]) {
            case 'a':
                pos += 1;
                if (text[pos] == 'm') {
                    if (findSubstring(text, pos, entity_map[AMP])) {
                        pos += entity_map[AMP].size();
                        return AMP;
                    }
                } else if (text[pos] == 'p') {
                    if (findSubstring(text, pos, "pos;")) {
                        pos += entity_map[APOS].size();
                        return APOS;
                    }
                }
                pos -= 1;
                return UNKNOWN;
            case 'f':
                if (findSubstring(text, pos, entity_map[FRASL])) {
                    pos += entity_map[FRASL].size();
                    return FRASL;
                }
                return UNKNOWN;
            case 'g':
                if (findSubstring(text, pos, entity_map[GT])) {
                    pos += entity_map[GT].size();
                    return GT;
                }
                return UNKNOWN;
            case 'l':
                if (findSubstring(text, pos, entity_map[LT])) {
                    pos += entity_map[LT].size();
                    return LT;
                }
                return UNKNOWN;
            case 'q':
                if (findSubstring(text, pos, entity_map[QUOT])) {
                    pos += entity_map[QUOT].size();
                    return QUOT;
                }
                return UNKNOWN;
            default:
                return UNKNOWN;
        }
        return UNKNOWN;
    }
public:
    string entityParser(string text) {
        string output; output.reserve(text.size());
        for (int i = 0; i < text.size(); ++i) {
            if (text[i] == '&') {
                auto x = parsePossibleEntity(text, ++i);
                if (x != UNKNOWN) {
                    output += token_map[x];
                } else {
                    output += "&";
                }
                --i;
            } else {
                text[i];
                output += text[i];
            }
        }
        return output;
    }
};
21300