Find common substring between two strings

有一段损失了定位信息的文字: plain_text = '我爱北京天安门, 天安门上放鞭炮', 要求还原这段文字在给定段落中尽可能相近的位置

这个段落数据结构大概长这样: paragraph = {'text': '佛曰我爱北京天安门, 天安门上太阳升...', chars': [{'text': '佛', 'box': [1, 2, 3, 4]}, {'text': '曰', 'box': [1, 2, 3, 4]}, ..., {'text': '我', 'box': [1, 2, 3, 4]}, ..., {'text': '门', 'box': [1, 2, 3, 4]}, ]}

其实这就是一个求最长公共子串的问题, 先简单粗暴实现了一发:

找出最大公共子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def find_longest_sub_str(string1, string2):
    answer = ''
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        for j in range(len2):
            lcs_temp = 0
            match = ''
            while (i + lcs_temp < len1) and (j + lcs_temp < len2) and string1[i + lcs_temp] == string2[j + lcs_temp]:
                match += string2[j + lcs_temp]
                lcs_temp += 1
            if len(match) > len(answer):
                answer = match
    return answer


if __name__ == '__main__':
    str_a = '我爱北京天安门, 天安门上放鞭炮'
    str_b = '佛曰 我爱北京天安门, 天安门上太阳升...'
    print(find_longest_sub_str(str_a, str_b))

按index取对应的box信息

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def find_longest_sub_str(string1, string2):
    answer = []
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        for j in range(len2):
            lcs_temp = 0
            match = []
            while (i + lcs_temp < len1) and (j + lcs_temp < len2) and string1[i + lcs_temp] == string2[j + lcs_temp]:
                match.append(j + lcs_temp)
                lcs_temp += 1
            if len(match) > len(answer):
                answer = match[:]
    return answer


if __name__ == '__main__':
    str_a = '我爱北京天安门, 天安门上放鞭炮'
    str_b = '佛曰 我爱北京天安门, 天安门上太阳升...'
    indexes = find_longest_sub_str(str_a, str_b)
    # 这里拦头去尾就可以从段落中拿到对应字的位置信息了

粗看起来貌似能交差, 但实际上很坑, 这玩意是O(N^2), 段落文字如果略长的话, 会慢到怀疑人生, 所以必须优化之, 放狗一搜, 发现标准库就有对应实现, 果断抄之

1
2
def find_longest_sub_str1(str_a, str_b):
    return SequenceMatcher(None, str_a, str_b).find_longest_match(0, len(str_a), 0, len(str_b))

跑了个分, 当字符串长度过长时, 人比人得死了...

# NOTE: I am not responsible for any expired content.
create@2021-11-23T06:56:34+08:00
update@2022-09-08T04:40:39+08:00
comment@https://github.com/ferstar/blog/issues/51

Find common substring between two strings

相关文章：