python - 通过与另一个列表匹配来检索列表中最长的匹配值 [Python 2.7]

Question

有两个要匹配的列表，li_a是给定的列表，由句子的字符序列组成，而li_b是单词的集合。

li_a = ['T','h','e','s','e','45','a','r','e','c','a','r','s']


li_b = ['T','Th','The','Thes','These','a','ar','are','c','ca','car','cars']

该过程是迭代地将 li_a 项与 li_b 项进行匹配。如果li_a的第一个字符与li_b项相似，则li_a的第一个字符与下一个字符连接，并重复该过程，直到达到到最长的匹配。然后，最长的期限应该被分割，这个过程将持续到最后。由于 li_a 中未出现在 li_b 中的未知字符和单词将按原样追加。

最终的作品应该是这样的:

new_li = ['These','45','are','cars']

尝试到目前为止，但这适用于两个字符串，不适用于列表，并且它不会检索未识别的单词。

def longest_matched_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
       for y in xrange(1, 1 + len(s2)):
           if s1[x - 1] == s2[y - 1]:
               m[x][y] = m[x - 1][y - 1] + 1
               if m[x][y] > longest:
                   longest = m[x][y]
                   x_longest = x
           else:
               m[x][y] = 0

    return s1[x_longest - longest: x_longest]

Answer 1

您可以使用两个 for 循环 和一个临时变量 来完成此操作，如下所示:

def longest_matched_substring(li1, li2):
    new_li = []
    tmp = ''
    for a in li1:
        tmp += a
        count = 0
        for b in li2:
            if tmp == b:
                count += 1
        if count == 0:
            tmp1 = tmp.replace(a, '')
            new_li.append(tmp1)
            tmp = a
    if li2.__contains__(tmp):
        new_li.append(tmp) 
    return new_li

输入:

li_a = ['T','h','e','s','e','45','a','r','e','c','a','r','s']
li_b = ['T','Th','The','Thes','These','a','ar','are','c','ca','car','cars']
print longest_matched_substring(li_a, li_b)

输出:

['These', '45', 'are', 'cars']

对于新的场景，可以修改函数如下:

def longest_matched_substring(li1, li2):
    new_li = []
    tmp = ''
    for a in li1:
        tmp += a
        count = 0
        for b in li2:
            if tmp == b:
                count += 1
        if count == 0:
            tmp1 = tmp.replace(a, '')

            new_li.append(tmp1)
            tmp = a
    if li_b.__contains__(tmp):
        new_li.append(tmp) 
    for e1 in new_li:
        tmp2 = e1
        rm = []
        for e2 in new_li:
            if e1 != e2:
                tmp2 += e2
                rm.append(e2)
                if tmp2 in li2:
                    new_li.insert(new_li.index(e1), tmp2) # if order matters
                    #new_li.append(tmp2) if order doesn't matter
                    for r in rm:
                        new_li.remove(r)
                    new_li.remove(e1)
                    rm = []
                    break
    return new_li

输入:

li_a = ['T','h','e','s','e','45','a','r','e','c','a','r','s']
li_b = ['T','Th','The','These','a','ar','are','c','ca','car','cars']
print longest_matched_substring(li_a, li_b)

输出:

['These', '45', 'are', 'cars']