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

long long int a_pow_n(long long int a, long long int n){
    if(n==0){
        return 1LL;
    } 
    if(n%2==0){
        long long int temp = a_pow_n(a, n/2);
        return (temp*temp)%MOD;
    } else{
        return (a*a_pow_n(a, n-1))%MOD;
    }
}

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int>word_id;
        int n = (int)words.size();
        for(int i=0;i<n;i++){
            string rev = words[i];
            reverse(rev.begin(), rev.end());
            word_id[rev] = i;
        }

        vector<vector<int>>ans;
        set<pair<int,int>>s;
        for(int i=0;i<n;i++){
            string a = words[i];
            string b = "";

            long long int hash_a = 0;
            long long int hash_ra = 0;

            for(int j=0;j<a.size();j++){
                hash_a = (hash_a*31)%MOD + (a[j] - 'a' + 1);
                hash_ra = (hash_ra*31)%MOD + (a[(int)a.size() - j - 1] - 'a' + 1);
            }

            long long int hash_b = 0;
            long long int hash_rb = 0;

            if(word_id.find(a) != word_id.end() && word_id[a] != i){
                s.insert({i, word_id[a]});
            }
            if(hash_a==hash_ra && word_id.find(b)!=word_id.end() && word_id[b]!=i){
                s.insert({word_id[b], i});
            }

            long long int pow_31 = 1;
            long long int pow_31_rev = 1;
            for(int j=0;j<(int)a.size()-1;j++){
                pow_31_rev = (pow_31_rev*31)%MOD;
            } 
            for(int j=(int)a.size()-1;j>=0;j--){
                char last = a[j];
                //cout<<a<<"-----"<<endl;
                a.pop_back();
                b.insert(b.begin(), last);

                hash_b = ((hash_b*31)%MOD + (last-'a'+1))%MOD;
                hash_rb = ((pow_31*(last-'a'+1))%MOD + hash_rb)%MOD;

                hash_a = ((hash_a - (last-'a'+1) + MOD)%MOD * a_pow_n(31, MOD-2))%MOD;
                hash_ra = (hash_ra - ((last-'a'+1)*pow_31_rev)%MOD + MOD)%MOD;

                //cout<<hash_a<<" "<<hash_ra<<"~~~~~~"<<endl;
                pow_31 = (pow_31*31)%MOD;
                pow_31_rev = (pow_31_rev*a_pow_n(31, MOD-2))%MOD;

                if(word_id.find(a) != word_id.end() && word_id[a] != i && hash_b == hash_rb ){
                    cout<<words[i]<<" "<<words[word_id[a]]<<endl;
                    s.insert({i, word_id[a]});
                }

                if(word_id.find(b) != word_id.end() && word_id[b] != i && hash_a==hash_ra ){
                    cout<<words[word_id[b]]<<" "<<words[i]<<endl;
                    s.insert({word_id[b], i});
                }
            }
        }

        for(pair<int,int>p: s){
            cout<<p.first<<" "<<p.second<<endl;
            vector<int>ans_entry;
                ans_entry.push_back(p.first);
                ans_entry.push_back(p.second);
                ans.push_back(ans_entry);
        }
        
        return ans;

    }
};
83216