子串模糊匹配(Python)

题目详情:

从字符串string开始完整匹配子串sub,返回匹配到的字符个数。

sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符,则说明不能完整匹配。

如果能完整匹配,返回匹配到的字符个数,如果有多种匹配方式,返回匹配字符数最少的那个,如果不能完整匹配,返回-1

输入描述:

第一行输入字符串string,长度小于10000

第二行输入子串sub,长度小于100

输出描述:

从string开头位置完整匹配sub,匹配到的字符个数。

示例1

输入

abcdefg
a?c

输出

3

示例2

输入

aabcddefg
a?c

输出

4

示例3

输入

aabcddefg
b?e

输出

-1

示例4

输入

aabcddefg
a?d

输出

5

代码解答:

s1 = input()
s2 = input()
n,m = len(s1),len(s2)
# 当两个字符串为空时,匹配数量为0输出0
if n == 0 or m == 0:
    print(0)
# 当匹配字符串长度大于原字符串时,不能匹配,输出-1
elif n < m:
    print(-1)
else:
    res = -1
    # 当匹配字符串第一个字符不是"?"时,
    # 若原字符串与匹配字符串第一个字符不相同,则无法向下继续匹配,跳出,直接输出-1
    if s2[0] != "?" and s1[0] != s2[0]:
        print(res)
    else:
        # 分别为原字符串与匹配字符串申请一个指针,并初始化指向第一个字符
        j, sj = 0, 0
        # 循环移动指针,直至到字符串尾部
        while j < n and sj < m:
            # 当匹配字符串不是指向"?"时,
            # 若两个字符串指向的字符不相同则不能继续匹配直接跳出输出-1
            if s2[sj] != "?" and s2[sj] != s1[j]:
                break
            # 当两个指针指向相同的字符时,两个指针向下移动一格,继续向下匹配
            elif s2[sj] == s1[j]:
                sj += 1
                j += 1
            # 当匹配字符串指针指向"?"时,查看"?"匹配数量是否大于3,大于则输出-1
            elif s2[sj] == "?":
                if j - sj > 3:
                    res = -1
                    break
                # 若两个字符串下一个指针指向字符相同,则跳过下一个,指针加2,继续向下
                if s2[sj+1] == s1[j+1]:
                    sj += 2
                    j += 2
                # 否则原字符串加一,匹配字符串指针不变,查看"?"最多匹配数量
                else:
                    j += 1
        # 若匹配字符串指针已经指向尾部(完全匹配)且结果数小于新的匹配数,则更新
        if sj >= m and j <= n and j > res:
            res = j
        print(res)

 


版权声明:本文为kingyuan666原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。