给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

枚举前缀后缀

import java.util.*;

class Solution {
    Map<String, Integer> indices = new HashMap<String, Integer>();

    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        for (int i = 0; i < n; ++i) {
            indices.put(new StringBuffer(words[i]).reverse().toString(), i);

        }

        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            String word = words[i];
            int m = words[i].length();
            for (int j = 0; j <= m; j++) {
                if (isPalindrome(word, j, m - 1)) {
                    int leftId = findWord(word, 0, j - 1);
                    if (leftId != -1 && leftId != i) {
                        ret.add(Arrays.asList(i, leftId));
                    }
                }
                if (j != 0 && isPalindrome(word, 0, j - 1)) {
                    int rightId = findWord(word, j, m - 1);
                    if (rightId != -1 && rightId != i) {
                        ret.add(Arrays.asList(rightId, i));
                    }
                }
            }
        }
        return ret;
    }

    public boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }

    public int findWord(String s, int left, int right) {
        return indices.getOrDefault(s.substring(left, right + 1), -1);
    }
}

字典树 + Manacher

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    private static String enrich(String word) {
        StringBuffer sb = new StringBuffer();
        sb.append('$');
        for (int i = 0; i < word.length(); ++i) {
            sb.append(word.charAt(i)).append('$');
        }
        return sb.toString();
    }

    private static boolean[][] getPalindromePrefixAndSuffix(String word) {
        if (word == null || word.length() == 0) {
            return new boolean[2][0];
        }
        boolean[][] ret = new boolean[2][word.length()];
        word = enrich(word);
        int[] p = new int[word.length()];
        int c = -1;
        int r = -1;

        // 0 1 2 3 4 5 6
        // # 1 # 1 # 1 #
        for (int i = 0; i < word.length(); ++i) {
            p[i] = i > r ? 1 : Math.min(p[2 * c - i], r - i + 1);
            while (i + p[i] < word.length() && i - p[i] >= 0 && word.charAt(i + p[i]) == word.charAt(i - p[i])) {
                p[i]++;
            }
            if (i + p[i] - 1 > r) {
                r = i + p[i] - 1;
                c = i;
            }

            if (i != 0 && i != word.length() - 1) {
                if (i - p[i] + 1 == 0) {
                    ret[0][(i + p[i] - 2) >> 1] = true;
                }

                if (i + p[i] == word.length()) {
                    ret[1][(i - p[i] + 2) >> 1] = true;
                }
            }
        }
        return ret;
    }

    /**
     * O(n * m)
     *
     * @param words
     * @return
     */
    private static List<List<Integer>> solve(String[] words) {

        List<List<Integer>> ret = new ArrayList<>();

        Trie prefixTrie = new Trie();
        Trie suffixTrie = new Trie();

        for (int i = 0; i < words.length; ++i) {
            prefixTrie.insert(words[i], i);
            suffixTrie.insert(new StringBuilder(words[i]).reverse().toString(), i);
        }

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];

            boolean[][] palindromePrefixAndSuffix = getPalindromePrefixAndSuffix(word);

            boolean[] prefix = palindromePrefixAndSuffix[0];
            boolean[] suffix = palindromePrefixAndSuffix[1];

            int[] suffixIndex = suffixTrie.query(word);

            int[] prefixIndex = prefixTrie.query(new StringBuilder(word).reverse().toString());

            int m = word.length();

            /**
             * 是否存在word完全逆序的字符串
             */
            if (suffixIndex[m] != -1 && suffixIndex[m] != i) {
                ret.add(Arrays.asList(i, suffixIndex[m]));
            }

            for (int j = 0; j < m; ++j) {
                /**
                 * word字符串 [0, j] 为回文串
                 * 需要 [j+1, m) 的字符串逆序后拼接到前面
                 */
                if (prefix[j]) {
                    if (prefixIndex[m - j - 1] != -1 && prefixIndex[m - j - 1] != i) {
                        ret.add(Arrays.asList(prefixIndex[m - j - 1], i));
                    }
                }

                /**
                 * word字符串 [j, m)为回文串
                 * 需要 [0, j-1] 的字符串逆序后拼接到后面
                 */
                if (suffix[j]) {
                    if (suffixIndex[j] != -1 && suffixIndex[j] != i) {
                        ret.add(Arrays.asList(i, suffixIndex[j]));
                    }
                }
            }
        }

        return ret;
    }

    public static List<List<Integer>> palindromePairs(String[] words) {
        if (words == null || words.length == 0) {
            return new ArrayList<>(0);
        }

        return solve(words);
    }
}

class Trie {

    private Node root;

    static class Node {
        Node[] children = new Node[26];
        int index = -1;
    }

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word, int index) {
        Node p = root;
        for (int i = 0; i < word.length(); ++i) {
            int path = word.charAt(i) - 'a';
            if (p.children[path] == null) {
                p.children[path] = new Node();
            }
            p = p.children[path];
        }
        p.index = index;
    }

    public int[] query(String word) {
        Node p = root;
        int[] ret = new int[word.length() + 1];
        Arrays.fill(ret, -1);
        ret[0] = root.index;
        for (int i = 0; i < word.length(); ++i) {
            int path = word.charAt(i) - 'a';
            if (p.children[path] == null) {
                break;
            }
            p = p.children[path];
            ret[i + 1] = p.index;
        }
        return ret;
    }
}