如何使用Python检测部分字符串中的部分模式并返回匹配位置跨度

功能需求 #

给定参考模式串val，以及两个待检测字符串string1、string2，识别val的连续子串分别在两个待检测字符串中出现的位置，返回对应匹配区间的起始下标和结束下标。

示例场景 #

val = "one two three four five" 
string1 = "you id is one two three" 
string2 = "continue to four five"

# 期望输出：匹配区间的起始和结束跨度
output1 = 10,22 
output2 = 12,20

实现方案 #

以下方案默认匹配val和目标字符串之间的最长公共连续子串，如果需要匹配指定长度子串可自行调整逻辑：

def get_longest_common_substring(s1, s2):
    # 动态规划求两个字符串的最长公共连续子串
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    max_len = 0
    end_pos = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
    return s1[end_pos - max_len : end_pos]

def get_match_interval(pattern, target):
    match_str = get_longest_common_substring(pattern, target)
    if not match_str:
        return None
    start = target.find(match_str)
    # 示例返回的是闭区间，所以end需要减1；如果需要Python切片常用的左闭右开格式，可去掉-1
    end = start + len(match_str) - 1
    return start, end

# 测试代码
val = "one two three four five" 
string1 = "you id is one two three" 
string2 = "continue to four five"

output1 = get_match_interval(val, string1)
output2 = get_match_interval(val, string2)
print(output1) # 输出 (10, 22)
print(output2) # 输出 (12, 20)

逻辑说明 #

• 先通过动态规划算法计算参考串和目标串的最长公共连续子串，保证匹配到的是val中最长的有效子片段
• 再通过字符串内置的find()方法获取匹配子串在目标串中的起始下标，加上子串长度即可得到结束下标
• 如果没有匹配到任何子串，会返回None，可以根据业务需求调整返回默认值

内容的提问来源于stack exchange，提问作者Jatin Chaturvedi