import java.util.*;

public class _336 {
    static class Solution1 {
        static class Tire {
            int index = -1;
            List<Integer> reversePalindromePart;
            Tire[] next = new Tire[26];

            Tire() {
                reversePalindromePart = new ArrayList<>();
            }
        }

        public List<List<Integer>> palindromePairs(String[] words) {
            //discuss的思路
            //对于 a + b是回文
            //1. a[0,i-1] + a[i,End] + b;
            //如果  a[i,End]是回文， a[0,i] == reverse(b);
            //  2. a + b[0,i] + b[i+1,End]
            //必须保证 b[0,i]是回文
            //创建Tire,逆序创建，如果  b[0,i]是回文，将index加入reversePalindromePart中,当单词结束，最后一个Tire
            //的index是当前单词的index
            Tire root = new Tire();
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < words.length; i++) {
                buildTire(words, i, root);
            }
            for (int i = 0; i < words.length; i++) {
                search(res, words[i], i, root);
            }
            return res;
        }

        public void search(List<List<Integer>> res, String word, int cur, Tire root) {
            for (int i = 0; i < word.length(); i++) {
                if (root == null) return;
                if (testP(word, i, word.length() - 1) && root.index != -1 && root.index != cur) {
                    //1. a[0,i-1] + a[i,End] + b;
                    res.add(Arrays.asList(cur, root.index));
                }
                root = root.next[word.charAt(i) - 'a'];
            }
            //2. a + b[0,i] + b[i+1,End]
            if (root == null) return;
            for (int j : root.reversePalindromePart) {
                if (cur != j) res.add(Arrays.asList(cur, j));
            }
        }

        public void buildTire(String[] words, int i, Tire root) {
            for (int j = words[i].length() - 1; j >= 0; j--) {
                if (testP(words[i], 0, j)) {
                    root.reversePalindromePart.add(i);
                }
                int x = words[i].charAt(j) - 'a';
                if (root.next[x] == null) root.next[x] = new Tire();
                root = root.next[x];
            }
            root.reversePalindromePart.add(i);
            root.index = i;
        }

        public boolean testP(String s, int l, int r) {
            while (l < r) {
                if (s.charAt(l++) != s.charAt(r--)) return false;
            }
            return true;
        }
    }

    static class Solution2 {
        public List<List<Integer>> palindromePairs(String[] words) {
            //hashMap解法
            //和Tire原理基本一致，只不过用HashMap存储逆序字符串罢了
            //1. build HashMap
            List<List<Integer>> res = new ArrayList<>();
            HashMap<String, List<Integer>> map = new HashMap<>();
            HashMap<String, Integer> endMap = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
                StringBuilder b = new StringBuilder();
                for (int j = words[i].length() - 1; j >= 0; j--) {
                    if (isPalindrome(words[i], 0, j)) {
                        map.computeIfAbsent(b.toString(), k -> new ArrayList<>()).add(i);
                    }
                    b.append(words[i].charAt(j));
                }
                String revs = b.toString();
                map.computeIfAbsent(revs, k -> new ArrayList<>()).add(i);
                endMap.put(revs, i);
            }
            //2.search
            for (int i = 0; i < words.length; i++) {
                for (int j = 0; j < words[i].length(); j++) {
                    String cur = words[i].substring(0, j);
                    if (endMap.containsKey(cur) && isPalindrome(words[i], j, words[i].length() - 1)) {
                        res.add(Arrays.asList(i, endMap.get(cur)));
                    }
                }
                for (int k : map.getOrDefault(words[i], Collections.emptyList())) {
                    if (k != i) res.add(Arrays.asList(i, k));
                }
            }
            return res;
        }

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

}