<p>You are given a <strong>0-indexed</strong> array of <strong>unique</strong> strings <code>words</code>.</p>

<p>A <strong>palindrome pair</strong> is a pair of integers <code>(i, j)</code> such that:</p>

<ul>
	<li><code>0 &lt;= i, j &lt; words.length</code>,</li>
	<li><code>i != j</code>, and</li>
	<li><code>words[i] + words[j]</code> (the concatenation of the two strings) is a <span data-keyword="palindrome-string">palindrome</span>.</li>
</ul>

<p>Return <em>an array of all the <strong>palindrome pairs</strong> of </em><code>words</code>.</p>

<p>You must write an algorithm with&nbsp;<code>O(sum of words[i].length)</code>&nbsp;runtime complexity.</p>

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

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dcba&quot;,&quot;lls&quot;,&quot;s&quot;,&quot;sssll&quot;]
<strong>Output:</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:</strong> The palindromes are [&quot;abcddcba&quot;,&quot;dcbaabcd&quot;,&quot;slls&quot;,&quot;llssssll&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;bat&quot;,&quot;tab&quot;,&quot;cat&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;battab&quot;,&quot;tabbat&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;a&quot;,&quot;a&quot;]
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>0 &lt;= words[i].length &lt;= 300</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

static const int64_t factor = 31;

static const int64_t p = 1000000007;

vector<int64_t> calc_powers() {
    vector<int64_t> res(300);
    res[0] = 1;
    for (int i = 1; i < 300; ++i) {
        res[i] = (res[i - 1] * factor) % p;
    }
    return res;
};

static const vector<int64_t> powers = calc_powers();

vector<int64_t> polyhash(const string& s) {
    vector<int64_t> res(s.size());
    for (int i = 0; i < s.size(); ++i) {
        res[i] = ((i ? res[i - 1] : 0) + static_cast<int64_t>(s[i]) * powers[i]) % p;
    }
    return res;
};

bool is_poly(const string& s, int size) {
    for (int j = 0; j < size / 2; ++j) {
        if (s[j] != s[size - 1 - j]) {
            return false;
        }
    }
    return true;
};

int64_t fn(int64_t diff) {
    return diff >= 0 ? diff : p + diff;
}

vector<pair<int, int>> get_pairs(const unordered_map<int64_t, vector<int>>& map
, const vector<string>& words, int curr_ind) {
    vector<pair<int, int>> res;
    auto s = words[curr_ind];
    auto hash_forward = polyhash(s);
    string s_reversed(s.rbegin(), s.rend());
    auto hash_backward = polyhash(s_reversed);
    reverse(hash_backward.begin(), hash_backward.end());

    for (int n_right_dropped = 0; n_right_dropped <= s.size(); ++n_right_dropped) {
        auto resid_size = s.size() - n_right_dropped;
        auto left_ind = resid_size / 2 - (resid_size % 2 ? 0 : 1);
        if (resid_size <= 1 || 
        (fn(hash_forward[resid_size - 1] - hash_forward[left_ind]) * powers[s.size() - 1 - left_ind - 1])  % p == (fn(hash_backward[0] - hash_backward[resid_size / 2]) * powers[resid_size / 2 - 1]) % p ) {
            if (is_poly(s, resid_size)) {
                auto hash_val = resid_size == s.size() ? 0 : hash_backward[resid_size];
                if (map.find(hash_val) != map.end()) {
                    for (auto ind : map.at(hash_val)) {

                        if (ind != curr_ind && string{s_reversed.begin(), s_reversed.begin() + n_right_dropped} == words[ind]) {
                            res.push_back({ind, curr_ind});
                        }
                    }
                }
            }
        }
    }

    std::swap(s_reversed, s);
    std::swap(hash_forward, hash_backward);
    reverse(hash_forward.begin(), hash_forward.end());
    reverse(hash_backward.begin(), hash_backward.end());

    for (int n_right_dropped = 0; n_right_dropped <= s.size(); ++n_right_dropped) {
        auto resid_size = s.size() - n_right_dropped;
        auto left_ind = resid_size / 2 - (resid_size % 2 ? 0 : 1);
        if (resid_size <= 1 || 
        (fn(hash_forward[resid_size - 1] - hash_forward[left_ind]) * powers[s.size() - 1 - left_ind - 1])  % p == (fn(hash_backward[0] - hash_backward[resid_size / 2]) * powers[resid_size / 2 - 1]) % p ) {
            if (is_poly(s, resid_size)) {
                int64_t hash_val = 0;
                for (int i = resid_size; i < s.size(); ++i) {
                    hash_val = (hash_val + static_cast<int64_t>(s[i]) * powers[i - resid_size]) % p; 
                }
                if (map.find(hash_val) != map.end()) {
                    for (auto ind : map.at(hash_val)) {
                        if (ind != curr_ind && string{s.end() - n_right_dropped, s.end()} == words[ind]) {
                            res.push_back({curr_ind, ind});
                        }
                    }
                }
            }
        }
    }
    return res;

}

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<int64_t, vector<int>> map;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i].empty()) {
                map[0].push_back(i);
            }
            else {
                map[polyhash(words[i]).back()].push_back(i);
            }
        }
        unordered_map<int, unordered_set<int>> res_map;
        for (int i = 0; i < words.size(); ++i) {
            auto arr = get_pairs(map, words, i);
            for (const auto& [first, second] : arr) {
                res_map[first].insert(second);
            }
        }
        vector<vector<int>> res;
        for (const auto& [key, arr] : res_map) {
            for (auto ind : arr) {
                res.push_back({key, ind});
            }
        }
        return res;
    }
};
167254