<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 <bits/stdc++.h> 

// #define MAIN_ACTIVE
// #define IO_FROM_FILE

using namespace std;
#define int64_t wadwafesfesfes21321300242142104210321
using int64_t = long long;
using pii = pair<int,int>;
using pil = pair<int,int64_t>;
using pli = pair<int64_t,int>;
using pll = pair<int64_t,int64_t>;
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define emp_back emplace_back
#define bitcount(x) __builtin_popcount((x))
#define mbin(val, cap) bitset<64>(val).to_string().substr(64 - cap)
#define PQ(x, y) priority_queue<x, vector<x>, y<x>>
// #define PQD(x, y) priority_queue<x, vector<x>, decltype(y)>
#define print(x) cout << "[ " << #x << " ]: " << x << "\n";
#define printc(x) cout << "[ " << #x << " ]: [", show(all(x), ", ", false), cout << "]\n";
#define e_ cout << "\n";
template <typename F, typename S> ostream& operator << (ostream& os, const pair<F, S>& duo) { return os << "(" << duo.first << ", " << duo.second << ")"; }
template <typename Iter> void show(Iter begin, Iter end, const char* sep = " ", bool is_end = true) { for(Iter it = begin; it != end; it++) cout << (it != begin ? sep : "") << *it; if(is_end) cout << "\n"; }
template<typename T, typename Cmp = less<T>> void get_unique(vector<T>& arr, Cmp compare = Cmp()){ sort(all(arr), compare); arr.erase(unique(all(arr)), arr.end()); }
mt19937_64 _GEN(chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename T>
T mrand(T begin, T end) {
    if constexpr (is_integral<T>::value){ uniform_int_distribution<T> _UNI_DIST(begin, end); return _UNI_DIST(_GEN); } 
    else if constexpr (is_floating_point<T>::value) { uniform_real_distribution<T> _UNI_DIST(begin, end); return _UNI_DIST(_GEN); }
}
int fastIO = []{ ios_base::sync_with_stdio(false); cin.tie(NULL); return 0; }();
//0down, 1right, 2up, 3left, 4upleft, 5downright, 6upright, 7downleft, 8stay
constexpr int dx[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
constexpr int dy[9] = {1, 0, -1, 0, -1, 1, -1, 1, 0};

template <uint64_t mod = 1'000'000'007>
struct Mint {
    uint64_t val;
    Mint() : val(0) {}
    Mint(int64_t _val) {
        _val %= mod;
        if (_val < 0) _val += mod;
        val = _val;
    }
    Mint& operator += (const Mint& other){ val += other.val; if(val >= mod) val -= mod; return *this; }
    Mint& operator -= (const Mint& other){ val += mod - other.val; if(val >= mod) val -= mod; return *this; }
    Mint& operator *= (const Mint& other){ val = (uint64_t)val * other.val % mod; return *this; }
    Mint& operator /= (const Mint& other){ return *this *= other.inv(); }
    Mint operator + (const Mint& other) const { return Mint(*this) += other; }
    Mint operator - (const Mint& other) const { return Mint(*this) -= other; }
    Mint operator * (const Mint& other) const { return Mint(*this) *= other; }
    Mint operator / (const Mint& other) const { return Mint(*this) /= other; }
    Mint pwr(int64_t expo) const {
        Mint res = 1;
        Mint cur = *this;
        while(expo){
            if(expo & 1) res *= cur;
            cur *= cur; expo >>= 1;
        }
        return res;
    }
    Mint inv() const { return pwr(mod - 2); }
    friend ostream& operator << (ostream& os, const Mint& m) { os << m.val; return os; }
    bool operator == (const Mint& other) const { return val == other.val; }
};

constexpr uint64_t MODS[] = {
    1'000'000'007,       // 1e9 + 7
    1'000'000'009,       // 1e9 + 9
    1'000'000'003,       // 1e9 + 3
    1'000'000'019,       // 1e9 + 19
    1'000'000'037,       // 1e9 + 37
    1'000'000'061,       // 1e9 + 61
    1'000'000'077,       // 1e9 + 77
    1'000'000'123,       // 1e9 + 123
    5'330'004'01, 
    7'356'327'91, 
    7'765'314'19,
    7'970'034'13
};

using mint1 = Mint<MODS[0]>;
using mint2 = Mint<MODS[1]>;
//need mint template
const int PRIME = 31;
const int nax = 301;
mint1 power1[nax];
mint2 power2[nax];

int makeId(char ch) {
    return ch - 'a' + 1;
}

class HashInterval {
private:
    vector<mint1> pref1;
    vector<mint2> pref2;
    bool is_rev;
    int n;
 
public:
    HashInterval() {}

    template <typename T>
    HashInterval(const T& s, bool _is_rev = false) { 
        is_rev = _is_rev;
        build(s); 
    }
    
    template <typename T>
    void build(const T& s) {
        n = s.size();
        pref1.resize(n);
        pref2.resize(n);
 
        if(is_rev){
            pref1[n - 1] = makeId(s[n - 1]);
            pref2[n - 1] = makeId(s[n - 1]);
            for(int i = n - 2; i >= 0; i--){
                pref1[i] = pref1[i + 1] * PRIME + makeId(s[i]);
                pref2[i] = pref2[i + 1] * PRIME + makeId(s[i]);
            }

            return;
        }
 
        pref1[0] = makeId(s[0]);
        pref2[0] = makeId(s[0]);
        for(int i = 1; i < n; i++){
            pref1[i] = pref1[i - 1] * PRIME + makeId(s[i]);
            pref2[i] = pref2[i - 1] * PRIME + makeId(s[i]);
        }
    }

    uint64_t combine(uint64_t code1, uint64_t code2) {
        return (code1 << 31) | code2;
    }
 
    uint64_t hashAt(int begin, int end) {
        if(is_rev){
            mint1 ans1 = pref1[begin];
            mint2 ans2 = pref2[begin];

            if(end != n - 1){
                ans1 -= pref1[end + 1] * power1[end - begin + 1];
                ans2 -= pref2[end + 1] * power2[end - begin + 1];
            }

            return combine(ans1.val, ans2.val);
        }
 
        mint1 ans1 = pref1[end];
        mint2 ans2 = pref2[end];
        if(begin){
            ans1 -= pref1[begin - 1] * power1[end - begin + 1];
            ans2 -= pref2[begin - 1] * power2[end - begin + 1];
        }

        return combine(ans1.val, ans2.val);
    }
};

#define HI HashInterval

int init = []{
    power1[0] = 1;
    power2[0] = 1;
    for(int i = 1; i < nax; i++){
        power1[i] = power1[i - 1] * PRIME;
        power2[i] = power2[i - 1] * PRIME;
    }
    return 0;
}();

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        auto makeID = [&](char ch) -> int {
            return ch - 'a' + 1;
        };

        const int n = words.size();
        umap<uint64_t, int> code_pos;
        for(int i = 0; i < n; i++){
            const string& s = words[i];
            mint1 code1 = 0;
            mint2 code2 = 0;
            for(int i = 0; i < s.size(); i++){
                code1 = code1 * PRIME + makeId(s[i]);
                code2 = code2 * PRIME + makeId(s[i]);
            }

            code_pos[(code1.val << 31) | code2.val] = i;
        }

        vector<vector<int>> ans;
        auto calc = [&](const string& s, int index) -> bool {
            const int m = s.size();
            HI for_hash(s);
            HI rev_hash(s, true);

            auto isPali = [&](int begin, int end) -> bool {
                if(begin >= end) return true;
                const int gap = end - begin + 1;
                const int mid = (end + begin) / 2;
                const int L1 = begin;
                const int R1 = mid - (1 & gap);
                const int L2 = mid + 1;
                const int R2 = end;

                return for_hash.hashAt(L1, R1) == rev_hash.hashAt(L2, R2);
            };

            for(int i = 0; i < m; i++){
                if(!isPali(i + 1, m - 1))
                    continue;
                auto it = code_pos.find(rev_hash.hashAt(0, i));
                if(it != code_pos.end() && it->second != index)
                    ans.push_back({index, it->second});
            }

            for(int i = m - 1; i >= 0; i--){
                if(!isPali(0, i - 1))
                    continue;
                auto it = code_pos.find(rev_hash.hashAt(i, m - 1));
                if(it != code_pos.end() && it->second != index)
                    ans.push_back({it->second, index});
            }

            return isPali(0, m - 1);
        };

        for(int i = 0; i < n; i++){
            if(words[i].empty()) continue;
            bool is_pali = calc(words[i], i);
            if(is_pali && code_pos.count(0)){
                ans.push_back({i, code_pos[0]});
                ans.push_back({code_pos[0], i});
            }
        }

        get_unique(ans);
        return ans;
    }
};

#ifdef MAIN_ACTIVE

void solve() {

#ifdef IO_FROM_FILE
    fout.close();
    fout.open(FILE_NAME + ".out", ios::app);
#endif
    
}

int main() {

    int test_count = 1;
    // cin >> test_count;
    while(test_count--)
        solve();

    return EXIT_SUCCESS;
}
#endif
175658