class Solution {
public:
        string addBoldTag(string s, vector<string>& dict) {
        constexpr char const *kBoldOpenTag = "<b>";
        constexpr char const *kBoldCloseTag = "</b>";

        vector<int> pattern_positions(s.size() + 1);

        for (auto& word : dict)
          FindPatternStartEndPos(s, word, &pattern_positions);

        string wrapped_res = "";

        int curr_tags_balance = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (pattern_positions[i] > 0) {
                if (curr_tags_balance == 0) wrapped_res += string(kBoldOpenTag);
                curr_tags_balance += pattern_positions[i];
            }
            else  if (pattern_positions[i] < 0) {
                curr_tags_balance += pattern_positions[i];
                if (curr_tags_balance == 0) wrapped_res += string(kBoldCloseTag);
            }

            wrapped_res += s[i];
        }
        if (pattern_positions.back() < 0) wrapped_res += string(kBoldCloseTag);
        return wrapped_res;
    }
private:
    void FindPatternStartEndPos(const string& t, const string& p, vector<int>* pattern_positions) {
        auto pi_function = CalculatePiFinction(t, p);

        for (int i = 0; i < pi_function.size(); ++i) {
            if (pi_function[i] == p.size()) {
                pattern_positions->at(i - p.size() + 1) += 1;
                pattern_positions->at(i + 1) += -1;
            }
        }
    }

    vector<int> CalculatePiFinction(const string& t, const string& p) {
        const string kDelim{ "#" };
        auto text = p + kDelim + t;
        vector<int> pi_function(text.size());

        for (int i = 1; i < text.size(); ++i) {
            int j = pi_function[i - 1];

            while (j && text[j] != text[i])
                j = pi_function[j - 1];

            if (text[i] == text[j]) pi_function[i] = j + 1;
            // else - 0
        }

        return vector<int>(pi_function.begin() + p.size() + kDelim.size(), pi_function.end());
    }
};