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

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

    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();

        std::vector<std::pair<std::string, int>> id_words;
        for (int i = 0; i < words.size(); i++) {
            id_words.emplace_back(words[i], i);
        }

        std::sort(id_words.begin(), id_words.end(), [](auto& a, auto& b) {
            return a.first.size() < b.first.size();
        });

        std::vector<std::string> reorder_words;
        for (const auto& p : id_words) {
            reorder_words.emplace_back(p.first);
        }
        std::vector<std::vector<int>> final_res;

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

        return final_res;
    }

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];
        }

        void prepare(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));
            }
        }

        bool isPalindrome(int i, int l, int r) {
            if (l > r) {
                return true;
            }
            return get_hash(i, l, r) == get_rhash(i, l, r);
        }

        std::vector<std::vector<int>> inner_solve(std::vector<std::string>& words) {
            std::map<uint64_t, std::vector<int>> mp;
            std::map<uint64_t, std::vector<int>> rmp;
            std::vector<std::vector<int>> res;
            for (int i = 0; i < words.size(); i++) {
                if (isPalindrome(i, 0, words[i].size() - 1)) {
                    for (const auto& id : mp[0]) {
                        res.emplace_back(std::vector<int>{id, i});
                        res.emplace_back(std::vector<int>{i, id});
                    }
                }
                for (int t = 0; t < words[i].size(); t++) {
                    auto h = hs[i][t + 1];
                    auto rh = rhs[i][t + 1];
                    if (isPalindrome(i, 0, words[i].size() - t - 2)) {
                        for (const auto& id : mp[rh]) {
                            res.emplace_back(std::vector<int>{id, i});
                        }
                    }
                    if (isPalindrome(i, t + 1, words[i].size() - 1)) {
                        for (const auto& id : rmp[h]) {
                            res.emplace_back(std::vector<int>{i, id});
                        }
                    }
                }
                mp[hs[i].back()].emplace_back(i);
                rmp[rhs[i].back()].emplace_back(i);
            }
            return res;
        }
        
        std::vector<std::vector<int>> solve(std::vector<std::string>& words) {
            prepare(words);
            auto res = inner_solve(words); 
            return res;
        }
    };
};
377348