Palindromic Pair

Split at every boundary

For each word and every split position, consider prefix | suffix. If the prefix is a palindrome, then any word equal to reverse(suffix) can precede the current word. If the suffix is a palindrome, any word equal to reverse(prefix) can follow it. Store every index for each word, not a single index, so duplicates and the empty string are handled. Exclude pairing a word with itself unless distinct indices exist.

The proof is concatenation-based: the non-palindromic remainder must be canceled by an exact reverse, while the palindromic side mirrors itself. With direct palindrome tests this is commonly O(n * L²) time for n words of maximum length L, plus output size, and O(nL) map storage; clarify if a trie is required for larger limits. Test empty string, duplicate words, a word that is already palindrome, and pairs in both orders. Deduplicate results because different splits can discover the same ordered pair.