给定两个字符串x和y，编写算法寻找字符串x的最长前缀同时是字符串y的后缀。

此题要求编写算法，寻找字符串x的最长前缀同时也是字符串y的后缀。

解题思路：

1.计算字符串x的前缀数组prefix_x。

2.将字符串y翻转得到字符串y_reverse。

3.计算字符串y_reverse的前缀数组prefix_y_reverse。

4.遍历prefix_x，寻找最大的index使得prefix_x[index]等于prefix_y_reverse[len(y)-1-index]，注意index从0开始。若没有找到这样的index，则最长前缀即为""。

5.最长前缀即为x的前index+1个字符。

代码如下：

def find_longest_prefix(x, y):
len_x = len(x)
len_y = len(y)
if len_x == 0 or len_y == 0:
return ""
prefix_x = [0] * len_x
prefix_x[0] = 0
j = 0
for i in range(1, len_x):
while j > 0 and x[i] != x[j]:
j = prefix_x[j-1]
if x[i] == x[j]:
j += 1
prefix_x[i] = j
y_reverse = y[::-1]
prefix_y_reverse = [0] * len_y
prefix_y_reverse[0] = 0
j = 0
for i in range(1, len_y):
while j > 0 and y_reverse[i] != y_reverse[j]:
j = prefix_y_reverse[j-1]
if y_reverse[i] == y_reverse[j]:
j += 1
prefix_y_reverse[i] = j
for i in range(len_x-1, -1, -1):
if prefix_x[i] == prefix_y_reverse[len_y-1-i]:
return x[:i+1]
return ""

测试：

>>> x = b'abcdefg'
>>> y = b'ghijkl'
>>> find_longest_prefix(x, y)
''
>>> x = b'abcdefg'
>>> y = b'ghijkabc'
>>> find_longest_prefix(x, y)
'abc'
>>> x = b'abcdefg'
>>> y = b'abcefghijkabcdefg'
>>> find_longest_prefix(x, y)
'abcdefg'