如何在两个字符串中找到最多的共享字符？（Python）

Question

yamxxopd
yndfyamxx

Output: 5

我不太确定如何在两个字符串之间找到最多共享字符数。例如（上面的字符串），最多共享的字符数是“yamxx”，长度为5个字符

xx不是一个解决方案，因为这不是最多的共享字符数。在这种情况下，最大的是yamxx，它有5个字符长，因此输出为5个字符

我对python和堆栈溢出非常陌生，因此非常感谢您的帮助

注意：它们在两个字符串中的顺序应该相同

Answer 1

&13； 第13部分,；

s1 = "yamxxopd"
s2 = "yndfyamxx"

# initializing counter
counter = 0

# creating and initializing a string without repetition
s = ""
for x in s1:
    if x not in s:
        s = s + x
for x in s:
    if x in s2:
        counter = counter + 1

# display the number of the most amount of shared characters in two strings s1 and s2
print(counter) # display 5

；

和#13；

Answer 2

下面是使用动态规划的简单、高效的解决方案

def longest_subtring(X, Y):
    m,n = len(X), len(Y)
    LCSuff = [[0 for k in range(n+1)] for l in range(m+1)] 
    result = 0 
    for i in range(m + 1): 
        for j in range(n + 1): 
            if (i == 0 or j == 0): 
                LCSuff[i][j] = 0
            elif (X[i-1] == Y[j-1]): 
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1
                result = max(result, LCSuff[i][j]) 
            else: 
                LCSuff[i][j] = 0
    print (result )
longest_subtring("abcd", "arcd")           # prints 2
longest_subtring("yammxdj", "nhjdyammx")   # prints 5

Answer 3

此解决方案从可能长度最长的子字符串开始。如果对于某个长度，不存在该长度的匹配子字符串，则它将移动到下一个较低的长度。这样，它可以在第一场成功的比赛中停止

s_1 = "yamxxopd"
s_2 = "yndfyamxx"

l_1, l_2 = len(s_1), len(s_2)

found = False
sub_length = l_1                                 # Let's start with the longest possible sub-string
while (not found) and sub_length:                # Loop, over decreasing lengths of sub-string
    for start in range(l_1 - sub_length + 1):    # Loop, over all start-positions of sub-string
        sub_str = s_1[start:(start+sub_length)]  # Get the sub-string at that start-position
        if sub_str in s_2:                       # If found a match for the sub-string, in s_2
            found = True                         # Stop trying with smaller lengths of sub-string
            break                                # Stop trying with this length of sub-string
    else:                                        # If no matches found for this length of sub-string
        sub_length -= 1                          # Let's try a smaller length for the sub-strings

print (f"Answer is {sub_length}" if found else "No common sub-string")

输出：

Answer is 5