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

#define ll long long int

class Solution {
public:
    ll powerBinExpo(ll x, ll n, ll mod)
    {
        // Time Complexity -> O(logn)
        ll ans = 1;
        while (n)
        {
            if (n & 1)
                ans = ans * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return ans;
    }

    ll modInverse(ll A, ll mod)
    {
        // If mod is Prime
        // Time Complexity -> O(log(mod))
        if (__gcd(A, mod) != 1)
            return -1;
        return powerBinExpo(A, mod - 2, mod);
    }

    pair<ll, ll> compute_hash(string const &s, vector<ll> &p1_powers, vector<ll> &p2_powers)
    {
        const int m = 1e9 + 9;
        long long hash_value1 = 0;
        long long hash_value2 = 0;

        for (int i = 0; i < s.size(); i++)
        {
            hash_value1 = (hash_value1 + (s[i] - 'a' + 1) * p1_powers[i]) % m;
            hash_value2 = (hash_value2 + (s[i] - 'a' + 1) * p2_powers[i]) % m;
        }
        return {hash_value1, hash_value2};
    }

    void compute(string const &s, vector<pair<ll,ll>> &prefix, vector<pair<ll,ll>> &suffix, int len, vector<ll> &p1_powers, vector<ll> &p2_powers){

        const int m = 1e9 + 9;
        long long hash_value1 = 0;
        long long hash_value2 = 0;

        prefix[0] = {0, 0};
        for (int i = 0; i < len; i++)
        {
            hash_value1 = (hash_value1 + (s[i] - 'a' + 1) * p1_powers[i]) % m;
            hash_value2 = (hash_value2 + (s[i] - 'a' + 1) * p2_powers[i]) % m;
            prefix[i+1] = {hash_value1, hash_value2};
        }

        hash_value1 = 0;
        hash_value2 = 0;

        suffix[len] = {0, 0};
        for (int i = len - 1; i >= 0; i--)
        {
            hash_value1 = (hash_value1 + (s[i] - 'a' + 1) * p1_powers[len - i - 1]) % m;
            hash_value2 = (hash_value2 + (s[i] - 'a' + 1) * p2_powers[len - i - 1]) % m;

            suffix[i] = {hash_value1, hash_value2};
        }
    }

    pair<ll,ll> getPrefixHash(vector<ll> &p1_powers, vector<ll> &p2_powers, vector<ll> &p1_inverse, vector<ll> &p2_inverse, vector<pair<ll,ll>> &prefix, int i, int j){
        const int m = 1e9 + 9;
        if(i > j)
            return {0, 0};
        ll temp1 = (prefix[j + 1].first - prefix[i].first + m) % m;
        temp1 = (temp1 * p1_inverse[i]) % m;

        ll temp2 = (prefix[j + 1].second - prefix[i].second + m) % m;
        temp2 = (temp2 * p2_inverse[i]) % m;
        return {temp1, temp2};
    }

    pair<ll,ll> getSuffixHash(vector<ll> &p1_powers, vector<ll> &p2_powers, vector<ll> &p1_inverse, vector<ll> &p2_inverse, vector<pair<ll,ll>> &suffix, int i, int j, int n){
        const int m = 1e9 + 9;
        if(i > j)
            return {0, 0};
        ll temp1 = (suffix[i].first - suffix[j+1].first + m) % m;
        temp1 = (temp1 * p1_inverse[n - j - 1]) % m;

        ll temp2 = (suffix[i].second - suffix[j+1].second + m) % m;
        temp2 = (temp2 * p2_inverse[n - j - 1]) % m;
        return {temp1, temp2};
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        const int m = 1e9 + 9;
        const int p1 = 31;
        const int p2 = 53;
        vector<ll> p1_powers(5001, 1);
        vector<ll> p1_inverse(5001, 1);
        vector<ll> p2_powers(5001, 1);
        vector<ll> p2_inverse(5001, 1);

        for (int i = 1; i <= 5000; i++)
        {
            p1_powers[i] = (p1_powers[i - 1] * p1) % m;
            p1_inverse[i] = modInverse(p1_powers[i], m);

            p2_powers[i] = (p2_powers[i - 1] * p2) % m;
            p2_inverse[i] = modInverse(p2_powers[i], m);
        }

        vector<vector<int>> ans;
        map<pair<ll,ll>,int> hashValue;
        for(int i = 0; i < words.size(); i++)
            hashValue[compute_hash(words[i], p1_powers, p2_powers)] = i;
        
        for(int i = 0; i < words.size(); i++){
            int len = words[i].size();
            vector<pair<ll,ll>> prefix(len+1), suffix(len+1);
            compute(words[i], prefix, suffix, len, p1_powers, p2_powers);

            for(int j = 0; j < len; j++){
                int l1 = j;
                int l2 = len - j - 1;
                if(l1 > l2){
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, len-1);
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, j-l2, j-1, len);
                    if(start == end){
                        pair<ll,ll> val = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j-l2-1, len);
                        if(hashValue.find(val) != hashValue.end() && hashValue[val] != i)
                            ans.push_back({i, hashValue[val]});
                    }
                }else if(l1 < l2){
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j-1, len);
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, j+l1);
                    if(start == end){
                        pair<ll,ll> val = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, j+l1+1, len-1, len);
                        if(hashValue.find(val) != hashValue.end() && hashValue[val] != i)
                            ans.push_back({hashValue[val], i});       
                    }
                }else{
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j-1, len);
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, len-1);
                    if(start == end){
                        if(hashValue.find({0, 0}) != hashValue.end() && hashValue[{0, 0}] != i){
                            ans.push_back({hashValue[{0, 0}], i});
                            ans.push_back({i, hashValue[{0, 0}]}); 
                        }
                    }
                }
            }

            for(int j = 0; j < len; j++){
                int l1 = j + 1;
                int l2 = len - j - 1;
                if(l1 > l2){
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, len-1);
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, j-l2+1, j, len);
                    if(start == end){
                        pair<ll,ll> val = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j-l2, len);
                        if(hashValue.find(val) != hashValue.end() && hashValue[val] != i)
                            ans.push_back({i, hashValue[val]});
                    }
                }else if(l1 < l2){
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j, len);
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, j+l1);
                    if(start == end){
                        pair<ll,ll> val = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, j+l1+1, len-1, len);
                        if(hashValue.find(val) != hashValue.end() && hashValue[val] != i)
                            ans.push_back({hashValue[val], i});       
                    }
                }else{
                    pair<ll, ll> start = getSuffixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, suffix, 0, j, len);
                    pair<ll, ll> end = getPrefixHash(p1_powers, p2_powers, p1_inverse, p2_inverse, prefix, j+1, len-1);
                    if(start == end){
                        if(hashValue.find({0, 0}) != hashValue.end() && hashValue[{0,0}] != i){
                            ans.push_back({hashValue[{0, 0}], i});
                            ans.push_back({i, hashValue[{0, 0}]}); 
                        }
                    }
                }
            }
        }
        return ans;
    }
};
209273