<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>

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>

struct Precalc {
    static constexpr size_t kMaxLen = 300;
    static constexpr uint64_t kBase = 57;

    constexpr Precalc() {
        M[0] = 1;
        for (int i = 1; i <= kMaxLen; i++) {
            M[i] = M[i - 1] * kBase;
        }
    }
    
    uint64_t M[kMaxLen + 1]{0};
};

constexpr Precalc pre;

class Solution {
public:
    std::vector<std::vector<int>> palindromePairs(std::vector<std::string>& words) {
        int n = words.size();

        auto res = Solver().solve(words);
        auto words_reverse = words;
        for (auto& word : words_reverse) {
            std::reverse(word.begin(), word.end());
        }

        auto res_2 = Solver().solve(words_reverse);
        for (const auto& p : res_2) {
            res.emplace_back(std::vector<int>{p[1], p[0]});
        }

        auto r_words = words;
        std::reverse(r_words.begin(), r_words.end());
        auto r_res = Solver().solve(r_words);
        for (const auto& p : r_res) {
            res.emplace_back(std::vector<int>{n - 1 - p[0], n - 1 - p[1]});
        }

        for (auto& word : r_words) {
            std::reverse(word.begin(), word.end());
        }
        auto r_res_2 = Solver().solve(r_words);
        for (const auto& p : r_res_2) {
            res.emplace_back(std::vector<int>{n - 1 - p[1], n - 1 - p[0]});
        }

        std::set<std::vector<int>> dedup_res(res.begin(), res.end());

        return {dedup_res.begin(), dedup_res.end()};
    }

private:
    

    struct Solver {
        std::vector<std::vector<uint64_t>> hs;
        std::vector<std::vector<uint64_t>> rhs;

        std::vector<uint64_t> hash_word(const std::string& word) {
            std::vector<uint64_t> h(word.size() + 1, 0);
            for (int i = 1; i <= word.size(); i++) {
                h[i] = h[i - 1] * pre.kBase + (word[i - 1]);
            }
            return h;
        }

        uint64_t get_hash(int i, int l, int r) { // l and r are 0 based
            if (l > r) {
                return 0;
            }
            return hs[i][r + 1] - hs[i][l] * pre.M[r - l + 1];
        }

        uint64_t get_rhash(int i, int l, int r) {
            if (l > r) {
                return 0;
            }
            int len = rhs[i].size() - 1;
            int rl = len - r - 1;
            int rr = len - l - 1;
            // handle out of bounds. ignore
            return rhs[i][rr + 1] - rhs[i][rl] * pre.M[r - l + 1];
        }
        
        std::vector<std::vector<int>> solve(std::vector<std::string>& words) {
            for (const auto& word : words) {
                hs.emplace_back(hash_word(word));
            }
            for (const auto& word : words) {
                std::string r_word = word;
                std::reverse(r_word.begin(), r_word.end());
                rhs.emplace_back(hash_word(r_word));
            }
            std::unordered_map<int, std::unordered_map<uint64_t, std::vector<int>>> mp;
            std::vector<std::vector<int>> res;
            for (int i = 0; i < words.size(); i++) {
                for (int c = 0; 2 * c <= words[i].size(); c++) {
                    // c is center, odd
                    if (2 * c < words[i].size()) {
                        auto lc = get_hash(i, 0, c - 1);
                        auto rc = get_rhash(i, c + 1, 2 * c);
                        if (lc == rc) {
                            auto remain_hash = get_hash(i, 2 * c + 1, words[i].size() - 1);
                            auto sz = words[i].size() - 1 - 2 * c;
                            for (const auto& id : mp[sz][remain_hash]) {
                                res.emplace_back(std::vector<int>{id, i});
                            }
                        }
                    }
                    // c is center, even
                    {
                        auto lc = get_hash(i, 0, c - 1);
                        auto rc = get_rhash(i, c, 2 * c - 1);
                        if (lc == rc) {
                            auto remain_hash = get_hash(i, 2 * c, words[i].size() - 1);
                            auto sz = words[i].size() - 1 - 2 * c + 1;
                            for (const auto& id : mp[sz][remain_hash]) {
                                res.emplace_back(std::vector<int>{id, i});
                            }
                        }
                    }
                }
                auto r_hash = rhs[i].back();
                auto wsz = words[i].size();
                mp[wsz][r_hash].emplace_back(i);
            }
            return res;
        }
    };
};

705094