首页 > 试题广场 >

字符串匹配

[编程题]字符串匹配

热度指数：6528 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛有两个字符串A和B,其中A串是一个01串,B串中除了可能有0和1,还可能有'?',B中的'?'可以确定为0或者1。寻找一个字符串T是否在字符串S中出现的过程,称为字符串匹配。牛牛现在考虑所有可能的字符串B,有多少种可以在字符串A中完成匹配。

例如:A = "00010001", B = "??"
字符串B可能的字符串是"00","01","10","11",只有"11"没有出现在字符串A中,所以输出3

输入描述:

输入包括两行,第一行一个字符串A,字符串A长度length(1 ≤ length ≤ 50),A中每个字符都是'0'或者'1'。
第二行一个字符串B,字符串B长度length(1 ≤ length ≤ 50),B中的字符包括'0','1'和'?'。

输出描述:

输出一个整数,表示能完成匹配的字符串种数。

示例1

输入

00010001
??

输出

算法知识视频讲解

Python3

doumihuoguo

截取***段，判断***段和b的当前字符是否相同或者b的当前字符是否为‘？’，如果不是则跳出判断，对下一个***段进行判断。若***段与b能匹配，则将当前片段加入集合。输出为集合大小。

str1, str2 = input(), input()
len1, len2 = len(str1), len(str2)

list1 = set()
flag = False
for i in range(len1-len2+1):
    substr = str1[i:i+len2]
    for j in range(len2):
        if substr[j] != str2[j] and str2[j] != '?':
            flag = False
            break
        else:
            flag = True
    if flag == True :
        list1.add(substr)

print(len(list1))

发表于 2024-11-08 10:45:00 回复(1)