如何找到两个字符串中最多共享字符？

Question

yamxxopd
yndfyamxx

Output: 5

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

xx 不是一个解决方案，因为这不是最大数量的共享字符。在本例中，最多的是 yamxx，它有 5 个字符长，因此输出将为 5。

我对 python 和堆栈溢出很陌生，所以任何帮助将不胜感激！

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

Answer 1

这是使用动态规划的简单、有效的解决方案。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 2longest_subtring("yammxdj", "nhjdyammx")   # prints 5

Answer 2

该解决方案从尽可能长的子串开始。如果对于某个长度，没有该长度的匹配子字符串，则它会移动到下一个较低的长度。这样，它可以在第一次成功匹配时停止。s_1 = "yamxxopd"s_2 = "yndfyamxx"l_1, l_2 = len(s_1), len(s_2)found = Falsesub_length = l_1                                 # Let's start with the longest possible sub-stringwhile (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-stringsprint (f"Answer is {sub_length}" if found else "No common sub-string")输出：答案是5

Answer 3

s1 = "yamxxopd"s2 = "yndfyamxx"# initializing countercounter = 0# creating and initializing a string without repetitions = ""for x in s1:    if x not in s:        s = s + xfor 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 s2print(counter) # display 5