class Solution {

public:

    vector<vector<int>> palindromePairs(vector<string>& words) {

        int size = words.size();

        int mul = 1000000007;

        int max_len = 0;

        vector<vector<int>> hash_pre(size, vector<int>());

        vector<vector<int>> hash_suf(size, vector<int>());

        vector<int> temp(2, 0);

        vector<vector<int>> ret;

        for (int i = 0; i < size; ++i) {

            hash_pre[i] = vector<int>(words[i].size(), 0);

            hash_suf[i] = vector<int>(words[i].size(), 0);

            if (words[i].size() == 0) continue;

            hash_pre[i][0] = words[i][0];

            hash_suf[i][words[i].size()-1] = words[i][words[i].size()-1];

            for (int j = 1; j < words[i].size(); ++j) {

                hash_pre[i][j] = hash_pre[i][j-1] * mul + words[i][j];

            }

            for (int j = (int)words[i].size()-2; j >= 0; --j) {

                hash_suf[i][j] = hash_suf[i][j+1] * mul + words[i][j];

            }

            max_len = max(max_len, (int)words[i].size());

        }

        vector<int> exp(max_len + 1, 0);

        exp[0] = 1;

        for (int i = 1; i <= max_len; ++i)

            exp[i] = exp[i-1] * mul;

        for (int i = 0; i < size; ++i)

            for (int j = 0; j < size; ++j) {

                if (i == j) continue;

                int len = words[i].size() + words[j].size();

                int hash_left = 0, hash_right = 0;

                int left_len = len / 2;

                if (left_len != 0) {

                    if (words[i].size() >= left_len) {

                        hash_left = hash_pre[i][left_len-1];

                    } else {

                        if (words[i].size() == 0)

                            hash_left = hash_pre[j][left_len-1];

                        else {

                            int right_pre = left_len - words[i].size();

                            hash_left = hash_pre[i][words[i].size() - 1] * exp[right_pre] + hash_pre[j][right_pre-1];

                        }

                    }

                }

                if (left_len != 0) {

                    if (words[j].size() >= left_len) {

                        hash_right = hash_suf[j][words[j].size()-left_len];

                    } else {

                        if (words[j].size() == 0)

                            hash_right = hash_suf[i][words[i].size()-left_len];

                        else {

                            int left_pre = left_len - words[j].size();

                            hash_right = hash_suf[j][0] * exp[left_pre] + hash_suf[i][words[i].size()-left_pre];

                        }

                    }

                }

                if (hash_left == hash_right) {

                    temp[0] = i, temp[1] = j;

                    ret.push_back(temp);

                }

            }

        return ret;

    }

};

class Solution {

    public List<List<Integer>> palindromePairs(String[] words) {

        Map<String, Integer> index = new HashMap<>();

        Map<String, Integer> revIndex = new HashMap<>();

        String[] revWords = new String[words.length];

        for (int i = 0; i < words.length; ++i) {

            String s = words[i];

            String r = new StringBuilder(s).reverse().toString();

            index.put(s, i);

            revIndex.put(r, i);

            revWords[i] = r;

        }

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

        result.addAll(findPairs(words, revWords, revIndex, false));

        result.addAll(findPairs(revWords, words, index, true));

        return result;

    }

    private static List<List<Integer>> findPairs(String[] words, String[] revWords, Map<String, Integer> revIndex, boolean reverse) {

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

        for (int i = 0; i < words.length; ++i) {

            String s = words[i];

            for (int k = reverse ? 1 : 0; k <= s.length(); ++k) {

                Integer j = revIndex.get(s.substring(k));

                if (j != null && j != i) {

                    if (s.regionMatches(0, revWords[i], s.length() - k, k)) {

                        result.add(reverse ? Arrays.asList(i, j) : Arrays.asList(j, i));

                    }

                }

            }

        }

        return result;

    }

}

class Solution(object):

    def palindromePairs(self, words):

        """

        :type words: List[str]

        :rtype: List[List[int]]

        """

        wordict = {}

        res = []

        for i in range(len(words)):

            wordict[words[i]] = i

        for i in range(len(words)):

            for j in range(len(words[i])+1):

                tmp1 = words[i][:j]

                tmp2 = words[i][j:]

                if tmp1[::-1] in wordict and wordict[tmp1[::-1]] != i and tmp2 == tmp2[::-1]:

                    res.append([i, wordict[tmp1[::-1]]])

                if j != 0 and tmp2[::-1] in wordict and wordict[tmp2[::-1]] != i and tmp1 == tmp1[::-1]:

                    res.append([wordict[tmp2[::-1]], i])

        return res