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

struct TrieNode
{
	TrieNode* children[26];
	int flag = -1;
	vector<int> index;
};

struct Trie
{
	TrieNode* root;
	Trie()
	{
		root = new TrieNode();
	}
	void insert(string word, int id)
	{
		TrieNode *temp = root;
		string word1;
		word1.resize(max(0, 2 * (int)word.size() - 1), '|');for (int j = 0; j < (int)word.size() * 2 - 1; j += 2) word1[j] = word[j / 2];
		vector<int> h(word1.size());
		int C = -1, R = 0;
		for (int i = 0; i < word1.size(); i++)
		{
			if (C + R > i)
				h[i] = min(h[2 * C - i], C + R - i);
			while (i - h[i] >= 0 && h[i] + i < word1.size() && word1[i - h[i]] == word1[i + h[i]]) h[i]++;
			if (C + R < i + h[i])
			{
				C = i; R = h[i];
			}
		}
		for (int i = 0; i < word.size(); i++)
		{
			if (!temp->children[word[i] - 'a']) temp->children[word[i] - 'a'] = new TrieNode();
			temp = temp->children[word[i] - 'a'];
			int j = 2 * i;
			int c = (j + 2 + (int)word1.size()) / 2;
			if (i != word.size() - 1 && h[c] + c == word1.size()) { temp->index.push_back(id);  }
		}
		temp->flag = id;
	}
};

class Solution {
private:
	Trie st;
	vector<vector<int>> ans;
	void manaker(string word, int id)
	{
		vector<int> h(word.size());
		int C = -1, R = 0;
		for (int i = 0; i < word.size(); i++)
		{
			if (C + R > i)
				h[i] = min(h[2 * C - i], C + R - i);
			while (i - h[i] >= 0 && h[i] + i < word.size() && word[i - h[i]] == word[i + h[i]]) h[i]++;
			if (C + R < i + h[i])
			{
				C = i; R = h[i];
			}
		}
		TrieNode* temp = st.root;
		if (temp->flag != -1 && temp->flag != id && word.size() / 2 == h[word.size() / 2] - 1) 
		{ 
			ans.push_back({ temp->flag, id }); 
			ans.push_back({ id,temp->flag});
		}
		for (int i = word.size() - 1; i >= 0; i -= 2)
		{
			if (!temp->children[word[i] - 'a']) return;
			temp = temp->children[word[i] - 'a'];
			int center = (i-2) / 2;
			if((i == 0 || h[center] == center + 1  )&& temp->flag != -1 && temp->flag != id )
			{
				ans.push_back({ temp->flag, id });
			}
		}
		for (auto i : temp->index)
			ans.push_back({ i,id });
	}

public:
	vector<vector<int>> palindromePairs(vector<string>& words) {
		for (int i = 0; i < words.size(); i++) st.insert(words[i], i);
		for (int i = 0; i < words.size(); i++)
		{
			string word; 
			word.resize(max(0,2 *(int) words[i].size() - 1), '|');
			for (int j = 0; j < (int)words[i].size() * 2 - 1; j += 2) word[j] = words[i][j / 2];
			manaker(word,i);
		}
		return ans;
	}
};

705094