查找两个字符串之间的所有公共子字符串，而不考虑大小写和ord

Question

因此，我从这个问题的答案Function to find all common substrings in two strings not giving correct output开始编写代码，并通过将字符串转换为小写，对其进行了一些修改，以适应大小写独立性（即AbCd与AbCd相同，依此类推）。但是，对于像'ABCDXGHIJ'和'ghijYAbCd'这样的字符串，它只返回['ghij']，而不是所需的输出['ABCD', 'GHIJ']。你知道吗

以下是其他示例：

• 'Bonywasawarrior'和'Bonywasxwarrior'（输出：['Bonywas', 'warrior', 'wa']，所需输出：['Bonywas', 'warrior']）
• '01101001'和'101010'（输出：['1010', '0', '1010', '01', '10', '01']，所需输出：['1010']）

这是我的密码：

t = int(input()) #t cases

while t > 0:
    A = str(input()) #1st string
    B = str(input()) #2nd string

    low_A = A.lower()
    low_B = B.lower()

    answer = ""
    anslist=[]
    for i in range(len(A)):
        common = ""
        for j in range(len(B)):
            if (i + j < len(A) and low_A[i + j] == low_B[j]):
                common += B[j]
            else:
                #if (len(common) > len(answer)): 
                answer = common
                if answer != '' and len(answer) > 1:
                    anslist.append(answer)
                common = ""

        if common != '':
            anslist.append(common)

    if len(anslist) == 0:
        print('[]') #print if no common substring
    else:
        print(anslist)
    t -= 1

Answer 1

您可以在while循环中增加一个偏移量，以使公共字符与相应索引的偏移量保持串联，直到它们变得不同。要查找最长、不重叠的公共子字符串，可以使用递归遍历子字符串分区的不同路径的函数，并返回子字符串长度最长的路径：

def common_strings(a, b, i=0, j=0):
    candidates = []
    len_a = len(a)
    len_b = len(b)
    if j == len_b:
        candidates.append(common_strings(a, b, i + 1, 0))
    elif i < len_a:
        offset = 0
        while i + offset < len_a and j + offset < len_b and a[i + offset].lower() == b[j + offset].lower():
            offset += 1
        if offset > 1:
            candidates.append([a[i: i + offset]] + common_strings(a, b, i + offset, j + offset))
        candidates.append(common_strings(a, b, i, j + 1))
    return candidates and max(candidates, key=lambda t: sorted(map(len, t), reverse=True))

以便：

print(common_strings('ABCDXGHIJ', 'ghijYAbCd'))
print(common_strings('Bonywasawarrior', 'Bonywasxwarrior'))
print(common_strings('01101001', '101010'))

输出：

['ABCD', 'GHIJ']
['Bonywas', 'warrior']
['1010']