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

class Solution {
public:
    vector<int> manacher_odd(string s) {
        int n = s.size();
        s = "$" + s + "^";
        vector<int> p(n + 2);
        int l = 1, r = 1;
        for(int i = 1; i <= n; i++) {
            p[i] = max(0, min(r - i, p[l + (r - i)]));
            while(s[i - p[i]] == s[i + p[i]]) {
                p[i]++;
            }
            if(i + p[i] > r) {
                l = i - p[i], r = i + p[i];
            }
        }
        return vector<int>(begin(p) + 1, end(p) - 1);
    }
    vector<int> manacher(string s) {
        string t;
        for(auto c: s) {
            t += string("#") + c;
        }
        auto res = manacher_odd(t + "#");
        return vector<int>(begin(res), end(res));
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        vector hashes(n, vector<pair<int, int>>());
        vector manachers(n, vector<int>());
        for(int i = 0; i < n; i++)
        {
            const int p = 31;
            const int m = 1e9 + 9;
            long long hash_value = 0;
            long long p_pow = 1;
            int len = words[i].size();
            hashes[i].assign(len + 1, make_pair(0, 0));
            manachers[i] = manacher(words[i]);
            for(int j = 0; j < len; j++)
            {
                hash_value = (hash_value + (words[i][j] - 'a' + 1) * p_pow) % m;
                p_pow = (p_pow * p) % m;
                hashes[i][j].first = hash_value;
            }
            reverse(words[i].begin(), words[i].end());
            hash_value = 0;
            p_pow = 1;
            for(int j = 0; j < len; j++)
            {
                hash_value = (hash_value + (words[i][j] - 'a' + 1) * p_pow) % m;
                p_pow = (p_pow * p) % m;
                hashes[i][j].second = hash_value;
            }
            if(len)
            {
                for(int j = len; j > 0; j--)
                {
                    hashes[i][j] = hashes[i][j - 1];
                }
                hashes[i][0] = {0, 0};
            }
        }

        vector<vector<int>> res;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                {
                    continue;
                }

                if(words[i].size() > words[j].size())
                {
                    int diff = words[i].size() - words[j].size();
                    int sz = hashes[i].size();
                    bool cond1 = hashes[j].back().second == hashes[i][sz - diff - 1].first;
                    bool cond2 = false;
                    if(diff & 1)
                    {
                        int k = words[i].size() - 1 - diff / 2;
                        cond2 |= (manachers[i][2 * k + 1] - 1) == diff;
                    }
                    else
                    {
                        int k = words[i].size() - 1 - diff / 2;
                        cond2 |= (manachers[i][2 * k + 2] - 1) == diff;
                    }
                    if(cond1 and cond2)
                    {
                        res.push_back({i, j});
                        continue;
                    }
                }
                else
                {
                    int diff = words[j].size() - words[i].size();
                    int sz1 = hashes[j].size();
                    int sz2 = hashes[i].size();
                    bool cond1 = hashes[i].back().first == hashes[j][sz1 - diff - 1].second;
                    bool cond2 = false;
                    if(diff & 1)
                    {
                        int k = diff / 2;
                        cond2 |= (manachers[j][2 * k + 1] - 1) == diff;
                    }
                    else
                    {
                        int k = diff / 2 - 1;
                        cond2 |= (manachers[j][2 * k + 2] - 1) == diff;
                    }
                    if(cond1 and cond2)
                    {
                        res.push_back({i, j});
                        continue;
                    }
                }

                // if(words[i].size() == 0)
                // {

                // }
            }
        }

        return res;
    }
};
259695