':type words: List[str]
:rtype: List[List[int]]'

def palindromePairs(self, words):

    def manacher(s, P):
        def preProcess(s):
            if (not s):
                return ['^', '$']
            T = ['^']
            for c in s:
                T += ['#', c]
            T += ['#', '$']
            return T
        T = preProcess(s)
        (center, right) = (0, 0)
        for i in xrange(1, (len(T) - 1)):
            i_mirror = ((2 * center) - i)
            if (right > i):
                P[i] = min((right - i), P[i_mirror])
            else:
                P[i] = 0
            while (T[((i + 1) + P[i])] == T[((i - 1) - P[i])]):
                P[i] += 1
            if ((i + P[i]) > right):
                (center, right) = (i, (i + P[i]))
    (prefix, suffix) = (collections.defaultdict(list), collections.defaultdict(list))
    for (i, word) in enumerate(words):
        P = ([0] * ((2 * len(word)) + 3))
        manacher(word, P)
        for j in xrange(len(P)):
            if ((j - P[j]) == 1):
                prefix[word[((j + P[j]) / 2):]].append(i)
            if ((j + P[j]) == (len(P) - 2)):
                suffix[word[:((j - P[j]) / 2)]].append(i)
    res = []
    for (i, word) in enumerate(words):
        for j in prefix[word[::(-1)]]:
            if (j != i):
                res.append([i, j])
        for j in suffix[word[::(-1)]]:
            if (len(word) != len(words[j])):
                res.append([j, i])
    return res
