<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 {
public:
    int p = 997;
    int b = 256;

    unordered_map<string, string> entityMap = {
        {"&quot;", "\""}, 
        {"&apos;", "'"}, 
        {"&amp;", "&"}, 
        {"&gt;", ">"}, 
        {"&lt;", "<"}, 
        {"&frasl;", "/"}
    };
    unordered_map<int, vector<string>> len2entity = {
        {4, {"&gt;", "&lt;"}},
        {5, {"&amp;"}},
        {6, {"&quot;", "&apos;"}},
        {7, {"&frasl;"}},
    };
    unordered_map<string, int> entity2hash;

    int powMod(int x, int pow) {
        if (pow == 0) return 1;        
        if (pow == 1) return x;
        int sq = powMod(x, pow/2);
        return (pow&1 ? ((x*sq)%p * sq) : (sq*sq)) % p;
    }

    string entityParser(string text) {
        int n = text.size();
        for (auto& e: entityMap) {
            int hash = 0;
            for (char c: e.first) {
                hash = (hash*b + c) % p;
            }
            entity2hash[e.first] = hash;
        }
        unordered_map<int, string> replaceList;
        for (int k = 4; k <= 7; k++) {
            int hash = 0;
            int i = 0;
            for (; i < k; i++) {
                hash = (hash*b + text[i]) % p;
            }
            int powModCache = powMod(b, k-1);
            i = k-1;
            while (true) {
                for (string& e: len2entity[k]) {
                    if (hash == entity2hash[e] && text.substr(i-k+1, k) == e)
                        replaceList[i-k+1] = e;
                }
                i++;
                if (i >= n) break;
                hash -= (powModCache*text[i-k])%p;
                hash = (hash + p) % p;
                hash = (hash*b + text[i]) % p;
            }
        }
        /*for (auto& p: replaceList) {*/
        /*    cout << p.first << " " << p.second << endl;*/
        /*}*/
        string res; res.reserve(n);
        for (int i = 0; i < n; i++) {
            if (replaceList.find(i) != replaceList.end()) {
                res += entityMap[replaceList[i]]; 
                i += replaceList[i].size() - 1;
            } else {
                res.push_back(text[i]);
            }
        }
        return res;
    }
};
38200