如何在python中以pythonic的方式（可能使用库函数）找到两个字符串之间最长的公共后缀前缀？

Question

假设我有两个字符串，s1 = "1234"和s2 ="34567"，所以s1和s2之间最长的公共后缀前缀是"34"。我想知道是否有任何pythonic方法可以快速获得匹配的部分（"34"）。你知道吗

我可以用下面这种天真的方式来做，但是我很想知道是否有一个有趣的库函数或算法来完成这个任务。你知道吗

s1 = "1234"
s2 = "34567"
length1 = len(s1) 
length2 = len(s2)

length = (length1 if length1<= length2 else length2)

for i in reversed(range(0, length)):
    if s1[-i - 1:] == s2[:i + 1]:
        print(s1[-i - 1:])
        break
    elif i > 0:
        continue
    else:
        print("no common suffix prefix")

输出：

34

我想要小巧又漂亮的东西！你知道吗

Answer 1

以下是两种替代实现：

你知道s1的后缀必须以s2[0]开头。所以用s1.find(s[0])来寻找候选的起点。此外，可以使用s2.startswith()而不是迭代s2。我不知道是否更快，但意图很清楚。你知道吗

def suffix_prefix_1(s1, s2):
    i = s1.find(s2[0])
    while i >= 0:
        if s2.startswith(s1[i:]):
            return s1[i:]

        i = s1.find(s2[0], i+1)

    return ''

如果您使用的是Python 3.8，则walrus操作符允许您这样编写：

def suffix_prefix_1A(s1, s2):
    while (i := s1.find(s2[0])) >= 0:
        if s2.startswith(s1[i:]):
            return s1[i:]

    return ''

使用s1.endswith()也可以做同样的事情：

def suffix_prefix_2(s1, s2):
    e= len(s2)
    while e > 0:
        if s1.endswith(s2[:e]):
            return s2[:e]
        e = s2.rfind(s1[-1], 0, e-1) + 1

    return ''

为了好玩，我们用正则表达式：

import re

def suffix_prefix_3(s1, s2):
    match = re.search(f"^{'?'.join(s1)}", s2)
    return match[0] if match else ''

Answer 2

算法中的逻辑是尽可能简单的，但是你肯定可以压缩符号。例如，检查大小为n的前缀和大小为n的后缀很简单：

s1[-n:] == s2[:n]

用于检查字符串长度的三元运算符是

min(len(s1), len(s2))

射程可以自行后退。range(x)的反面是

range(x - 1, -1, -1)

您可以创建一个迭代器来检查n的每个递减值，并返回第一个非零结果。幸运的是，next接受第二个参数，如果迭代器为空，则该参数表示默认值：

common = next((s2[:n] for n in range(min(len(s1), len(s2)) - 1, -1, -1) if s1[-n:] == s2[:n]), '')

这是必须的一行。更清晰的解决方案可能是：

def common_fix(s1, s2):
    steps = range(min(len(s1), len(s2)) - 1, -1, -1)
    return next((s2[:n] for n in steps if s1[-n:] == s2[:n]), '')

作为一项规则，保持你的功能和印刷分开。获取一个值，然后处理它（无论是通过打印还是其他方式）

Answer 3

这样做有效：

s1="1234"
s2="34567"
for i in range(len(s1)):
    if s1[i] == s2[0]:
        if s1[i::] in s2[0:len(s1[i::])]:
            print(s1[i::])

for循环查找s1的长度。然后迭代该长度。如果s1[i]等于s2的开头，它检查s1[i::]是否在s2中。如果这是真的，它将输出s1[i::]