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

'''
palindrome pair: pair of integers (i, j)
    i != j
    words[i] + words[j] is a palindrome

Return an array of all palindrome pairs.

Brute force: O(n^2 * k), for word length k.

Aim is to get ~O(nk).

My first intuition is... perhaps we can just do this with a dictionary lookup?

Index each word both directly and in reverse
    cat --> [3]
    tac --> [3]

Then for cat, we could have the following palindromes...
    cattac # easy case
    catac # also easy
    catxxxtac # hard case due to asymmetry.

Ok, but I think we can handle all of these:
- Case 1: exact reflection
    - Just search for the word's reflection in the index.
- Case 2: len(prefix) > len(suffix)
    - This means that the end of the prefix is a palindrome.
    - Partition the prefix into [A] + [B], where B is a palindrome, and search for the reflection of A.
- Case 3: len(prefix) < len(suffix)
    - Reverse both prefix and suffix
        [cat] + [xxxtac] --> [catxxx] + [tac]
    - Now defer to case 2.
    - Since we're looking for palindromes, we don't even need to do a second reversal.

How do we do this efficiently?
- Dict lookup for suffix: fine, O(k) for a length-k string.
- Checking multiple prefixes, where each suffix is k
    - Need: linear-time algorithm to find all palindromes in a string.
            >> this gives us all the prefixes of a string for which we need to find reflections
            trie to do the lookup for reflections in linear time
            catxxx
                do you have xxxtac?
                xxtac?
                xtac?
                tac?
            So we need to index the strings in reverse. Should be fine.

How do we find all palindromes of a string in linear time?
Obviously there is the O(n^2) solution.

Manacher's algorithm comes to mind... IIRC the idea is that you keep track of the righthand edge of your palindrome as you scan across... or something like that...

I'm not going to write the entire linear-time algorithm here. It would take too long.

Instead, I am going to write the key pieces *minus* the linear-time palindrome identification
'''

def is_palindrome(word, i: int, j: int) -> bool:
    while i < j:
        if word[i] != word[j]:
            return False
        i += 1
        j -= 1
    return True

def manachers_palindrome_suffixes(s: str):
    # Preprocess the string to handle even-length palindromes
    t = '#'.join(f'^{s}$')
    n = len(t)
    P = [0] * n  # Array to store the radius of palindromes
    C = R = 0    # C is the center, R is the rightmost boundary

    for i in range(1, n - 1):
        mirror = 2 * C - i  # Mirror of i with respect to C

        if i < R:
            P[i] = min(R - i, P[mirror])

        # Try to expand the palindrome centered at i
        while t[i + P[i] + 1] == t[i - P[i] - 1]:
            P[i] += 1

        # If the palindrome expanded past R, adjust the center and right boundary
        if i + P[i] > R:
            C = i
            R = i + P[i]

    # Now, gather palindromic suffix starts
    palindromic_suffix_starts = []
    m = len(s)

    # We want the palindromes that end at the last character of the original string
    for i in range(n - 2, 0, -1):
        if i + P[i] == n - 2:  # Check if the palindrome reaches the end of the original string
            start_idx = (i - P[i]) // 2
            palindromic_suffix_starts.append(start_idx)

    print(s, palindromic_suffix_starts)
    return palindromic_suffix_starts[::-1]

'''
Returns a list of indices such that the suffix of word[:i] is a palindrome

catt --> [2, 3]
'''
def compute_palindrome_suffixes(word: str) -> list[int]:
    return manachers_palindrome_suffixes(word)
    res = []
    for i in range(len(word)):
        if is_palindrome(word, i, len(word) - 1):
            res.append(i)
    res.append(len(word))
    return res

class Trie():

    def __init__(self):
        self.idx = -1
        self.children = {}
    
    def add_word(self, word: str, idx: int) -> None:
        t = self
        for ch in word:
            if ch not in t.children:
                t.children[ch] = Trie()
            t = t.children[ch]
        t.idx = idx
    

def palindrome_pairs(words: list[str]) -> list[list[int]]:
    # indexing
    t = Trie()
    for word_idx, word in enumerate(words):
        t.add_word(word[::-1], word_idx)

    # search
    res = []
    for word_idx, word in enumerate(words):
        palindrome_suffixes = compute_palindrome_suffixes(word)

        word_ptr = 0
        trie_ptr = t
        for i in palindrome_suffixes:
            # suppose the word is catxxx
            # we want to know if xxxtac, xxtac, xtac, or tac are in the corpus
            # therefore we index all the words in reverse
            # and we search for prefixes normally... cat (for tac), catx (for xtac), etc.
            while word_ptr < i:
                c = word[word_ptr]
                if c not in trie_ptr.children:
                    break
                trie_ptr = trie_ptr.children[c]
                word_ptr += 1
            
            if word_ptr != i:
                # hopeless
                break
            
            if trie_ptr.idx >= 0 and trie_ptr.idx != word_idx:
                res.append((word_idx, trie_ptr.idx))
            
    return res


class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        forward = palindrome_pairs(words)
        backward = palindrome_pairs([word[::-1] for word in words])
        backward = [(j,i) for i, j in backward]
        return list(set(forward + backward))
71501