python - 也是第二个字符串中的子字符串的最长前缀

Question

此代码（改编自前缀-后缀代码）对于较大的语料库非常慢：

s1 = ' gaf dggeg'
s2 = 'ada gaf rd'

输出：gaf

def pref_also_substr(s):
    n = len(s)
    for res in range(n, 0, -1):
        prefix = s[0: res]
        if (prefix in s1):
            return res

    # if no prefix and string2 match occurs

    return 0

任何有效替代方案的选择？

Answer 1

我有另一种方法来解决这个问题。首先，您可以找到所有子字符串s2并替换字典d中最大大小的键。

s2 = "'adagafrd'"
# Get all substrings of string 
# Using list comprehension + string slicing 
substrings = [test_str[i: j] for i in range(len(test_str))
       for j in range(i + 1, len(test_str) + 1)]

现在您可以使用startswith()函数从该子字符串列表中检查最长前缀并比较子字符串的大小。

s1 = 'gafdggeg'
d={}
for substring in substrings:
    if s1.startswith(substring):
        if not d:
            d[substring]=len(substring)
        else:
            if len(substring)>list(d.values())[0]:
                d={}
                d[substring]=len(substring)
print(d)

输出：

{'gaf': 3}

Answer 2

def f(s1, s2):
    for i in range(len(s1)):
        i += 1
        p = s1[:i]
        if p in s2:
            s2 = s2[s2.index(p):]
        else: 
            return i - 1

检查从长度 1 开始的前缀。如果找到前缀，则丢弃创建的前缀后面的字符并继续搜索。