在这种情况下如何获得两个字符串的交集？

Question

我有两个字符串：

str1 = "123147"
str2 =    "1474671231"

str1的结尾和str2("147")的开头有一些相似的部分，我想找到这个相似部分的长度，所以我试着:

for ch in str1:
    if ch == str2[0]:
        start_idx = len(str1) - date.index(ch)
        break

然而问题是，如果 str1 的开头与 str2 ("1") 的开头相同，并且如果我反转检查顺序，它仍然有这个问题（"7"）。有什么简单的方法可以解决吗？

最重要的是，我只想检查str1的结尾和str2的开头，而忽略其他部分，例如str1中的"1231" str2 应该被忽略。

Answer 1

试试这个，通过反转字符串得到最大匹配长度

str1 = "123147"
str2 = "147467"

result = 0
for i in range(len(str2)):
    temp = str2[:i + 1]
    if str1.endswith(temp):
        result = len(temp)
print(result)

Answer 2

尝试str1的所有后缀似乎没有问题，从最长的开始：

def intersection_length(str1, str2):
    for i in range(max(0, len(str2) - len(str1), len(str1))):
        if str2.startswith(str1[i:]):
            return len(str1) - i
    return 0

运行为：

str1 = "12314755"
str2 = "14755467"
print(intersection_length(str1, str2))  # 5

Answer 3

一种可能的方法是使用正则表达式，并以巧妙的方式连接字符串：

import re

C = '#'
result = len(re.findall(r'^(\w*).*$', str2 + C + str1)[0])

这里的假设是 str1 和 str2 都不包含字符 C.

另一个解决方案（具有最佳复杂性，即在处理长字符串时与其他方法相比速度非常快，但显然比您需要的更复杂）：

def longest_prefix_suffix(str1, str2):
    n = min(len(str1), len(str2))
    lps = [0] * n
    l = 0
    i = 1
    while i < n:
        if str1[i] == str2[l]:
            l += 1
            lps[i] = l
            i += 1
        else:
            if l != 0:
                l = lps[l - 1]
            else:
                lps[i] = 0
                i = i + 1
    return lps[n - 1]

在这种情况下如何获得两个字符串的交集？

How to get the intersection of two strings in this situation?

python

algorithm

python-3.x