<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:
    static const int N = 305;
    static const int MOD1 = 127657753, MOD2 = 987654319;
    static const int p1 = 137, p2 = 277;
    static int ip1, ip2;
    static pair<int, int> pw[N], ipw[N];

    int power(long long n, long long k, const int mod) {
        int ans = 1 % mod;
        n %= mod;
        if (n < 0)
            n += mod;
        while (k) {
            if (k & 1)
                ans = (long long)ans * n % mod;
            n = (long long)n * n % mod;
            k >>= 1;
        }
        return ans;
    }

    void prec() {
        pw[0] = {1, 1};
        for (int i = 1; i < N; i++) {
            pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1;
            pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2;
        }
        ip1 = power(p1, MOD1 - 2, MOD1);
        ip2 = power(p2, MOD2 - 2, MOD2);
        ipw[0] = {1, 1};
        for (int i = 1; i < N; i++) {
            ipw[i].first = 1LL * ipw[i - 1].first * ip1 % MOD1;
            ipw[i].second = 1LL * ipw[i - 1].second * ip2 % MOD2;
        }
    }

    struct Hashing {
        int n;
        string s;                  // 0 - indexed
        vector<pair<int, int>> hs; // 1 - indexed

        Hashing() {}
        Hashing(string _s) {
            n = _s.size();
            s = _s;
            hs.emplace_back(0, 0);
            for (int i = 0; i < n; i++) {
                pair<int, int> p;
                p.first = (hs[i].first + 1LL * Solution::pw[i].first * s[i] %
                                             Solution::MOD1) %
                          Solution::MOD1;
                p.second = (hs[i].second + 1LL * Solution::pw[i].second * s[i] %
                                               Solution::MOD2) %
                           Solution::MOD2;
                hs.push_back(p);
            }
        }

        pair<int, int> get_hash(int l, int r) { // 1 - indexed
            assert(1 <= l && l <= r && r <= n);
            pair<int, int> ans;
            ans.first = (hs[r].first - hs[l - 1].first + Solution::MOD1) * 1LL *
                        Solution::ipw[l - 1].first % Solution::MOD1;
            ans.second = (hs[r].second - hs[l - 1].second + Solution::MOD2) *
                         1LL * Solution::ipw[l - 1].second % Solution::MOD2;
            return ans;
        }

        pair<int, int> get_hash() { return get_hash(1, n); }
    };

    vector<vector<int>> palindromePairs(vector<string>& words) {

        std::map<pair<int, int>, vector<int>> mp;

        vector<vector<int>> v;
        set<pair<int, int>> st;
        int n = words.size();
        prec();

        vector<int> null_v;

        for (int i = 0; i < n; i++) {
            if (words[i] == "") {
                null_v.push_back(i);
                continue;
            }
            string ss = words[i];
            reverse(ss.begin(), ss.end());
            Hashing hs(ss);
            mp[hs.get_hash()].push_back(i);
        }
        for (int i = 0; i < n; i++) {
            if (words[i] == "")
                continue;
            string ss = words[i];
            reverse(ss.begin(), ss.end());
            Hashing hs(words[i]);
            Hashing hsr(ss);
            int sz = words[i].size();
            for (int j = 1; j <= sz; j++) {

                if (j < sz) {

                    {
                        auto pit = hs.get_hash(j + 1, sz);
                        auto pitr = hsr.get_hash(1, sz - j);
                        auto phval = hs.get_hash(1, j);
                        if (pit == pitr) {
                            if (mp.find(phval) != mp.end()) {
                                for (auto k : mp[phval]) {
                                    if (k == i)
                                        continue;
                                    // v.push_back({i, k});
                                    st.insert({i, k});
                                }
                            }
                        }
                    }
                    // {
                    // 	auto shval = hsr.get_hash(1, j);
                    // 	auto sitr = hsr.get_hash(j + 1, sz);
                    // 	auto sit = hs.get_hash(1, sz - j);

                    // 	if (sitr == sit) {
                    // 		if (mp.find(shval) != mp.end()) {
                    // 			for (auto k : mp[shval]) {
                    // 				if (k == i)continue;
                    // 				// v.push_back({k, i});
                    // 				st.insert({k, i});
                    // 			}
                    // 		}
                    // 	}

                    // }
                }

                else {
                    auto hval = hs.get_hash(1, j);
                    if (hs.get_hash() == hsr.get_hash()) {
                        for (auto k : mp[hval]) {
                            if (k == i)
                                continue;
                            // v.push_back({i, k});
                            // v.push_back({k, i});
                            st.insert({k, i});
                            st.insert({i, k});
                        }
                        for (auto k : null_v) {
                            if (k == i)
                                continue;
                            st.insert({k, i});
                            st.insert({i, k});
                        }
                    } else {
                        for (auto k : mp[hval]) {
                            if (k == i)
                                continue;
                            // v.push_back({i, k});
                            st.insert({i, k});
                        }
                    }
                }
                if (j > 1) {
                    auto shval = hs.get_hash(j, sz);
                    auto sitr = hs.get_hash(1, j - 1);
                    auto sit=hsr.get_hash(sz-j+2,sz);
                   

                        if (sitr == sit) {
                        if (mp.find(shval) != mp.end()) {
                            for (auto k : mp[shval]) {
                                if (k == i)
                                    continue;
                                // v.push_back({k, i});
                                st.insert({k, i});
                            }
                        }
                    }
                }
            }
        }
        for (auto [i, j] : st) {
            v.push_back({i, j});
        }
        return v;
    }
};

// Define static members outside the class
pair<int, int> Solution::pw[Solution::N];
pair<int, int> Solution::ipw[Solution::N];
int Solution::ip1;
int Solution::ip2;

436174