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

// 1490704才是数组至少设置的大小边界值
int children[1490705][26], r_children[1490705][26], isEnd[1490705], r_isEnd[1490705];
class Solution {
private:
    vector<vector<int>> ret;
    int reverCnt = 0, orderCnt = 0;
public:
    void insert(const string& word, const int& index) {
        int p1 = 0, p2 = 0, ch = 0;
        int n = word.size();
        for(int i = 0; i < n; ++i) {
            ch = word[i] - 'a';
            if(!children[p1][ch]) {
                children[p1][ch] = ++orderCnt;
            }
            p1 = children[p1][ch];

            ch = word[n - 1 - i] - 'a';
            if(!r_children[p2][ch]) {
                r_children[p2][ch] = ++reverCnt;
            }
            p2 = r_children[p2][ch];
        }
        isEnd[p1] = index;
        r_isEnd[p2] = index;
    }

    bool isPalindrome(const string& word, int i, int j) {
        while(i < j) {
            if(word[i++] != word[j--]) return false;
        }
        return true;
    }

    void search(const string& word, const int& index) {
        bool flag1 = true, flag2 = true;
        int p1 = 0, p2 = 0, ch = 0, n = word.size();
        for(int i = 0; i < n; ++i) {
            ch = word[i] - 'a';
            // 与后缀树匹配
            if(flag2) {
                if(r_isEnd[p2] && isPalindrome(word, i, word.size() - 1)) {
                    ret.push_back({index - 1, r_isEnd[p2] - 1});
                }
                if(!r_children[p2][ch]) {
                    flag2 = false;
                } else {
                    p2 = r_children[p2][ch];
                }
            }

            ch = word[n - 1 - i] - 'a';
            // 与前缀树匹配
            if(flag1) {
                if(isEnd[p1] && isPalindrome(word, 0, n - 1 - i)) {
                    ret.push_back({isEnd[p1] - 1, index - 1});
                }
                if(!children[p1][ch]) {
                    flag1 = false;
                } else {
                    p1 = children[p1][ch];
                }
            }
            if(!flag1 && !flag2) return;
        }
        if(flag2 && r_isEnd[p2] && r_isEnd[p2] != index) {
            ret.push_back({index - 1, r_isEnd[p2] - 1});
        }
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        for(int i = 0; i < words.size(); ++i) {
            insert(words[i], i + 1);
        }
        for(int i = 0; i < words.size(); ++i) {
            search(words[i], i + 1);
        }
        memset(children, 0, (orderCnt + 1)*sizeof(children[0]));
        memset(r_children, 0, (reverCnt + 1)*sizeof(r_children[0]));
        memset(isEnd, 0, (orderCnt + 1)*sizeof(isEnd[0]));
        memset(r_isEnd, 0, (reverCnt + 1)*sizeof(r_isEnd[0]));
        return ret;
    }
};
200869