# KMP solution in Python

• ``````    def _LPS(self, s):
'''
s: str
'''
# compute LPS
s_reversed = s[::-1]
s_cat = s + '#' + s_reversed
# auxiliary LPS array
lps = [0] * len(s_cat)
q = 0
for i in range(1, len(s_cat)):
# print(q, s_cat[q], s_cat[i])
while q and s_cat[q] != s_cat[i]:
q = lps[q - 1]
if s_cat[q] == s_cat[i]:
q += 1
lps[i] = q
l = lps[-1]
while l:
yield l
l = lps[l - 1]
yield l

def palindromePairsKMP(self, words: list):
word2idx = {t[1]: t[0] for t in enumerate(words)}
pairs = set()
for j, _ in enumerate(words):
# find palindrome prefix/suffix of words[j],
# reverse the remaining part,
# check its existence in the word2idx
for prefix_len in self._LPS(words[j]):
remaining = words[j][prefix_len:][::-1]
i = word2idx.get(remaining)
if i is not None and i != j: pairs.add((i, j))

for prefix_len in self._LPS(words[j][::-1]):
remaining = words[j][:len(words[j]) - prefix_len][::-1]
i = word2idx.get(remaining)
if i is not None and i != j: pairs.add((j, i))
pairs = sorted(map(lambda x: list(x), pairs))
print(pairs)
return pairs
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.