首页 > 试题广场 >

字符串匹配

[编程题]字符串匹配

热度指数：6198 时间限制：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
??

输出

算法知识视频讲解

morethanthis

var count = 0
func main() {
	var A,B string
	fmt.Scanf("%s",&A)
	fmt.Scanf("%s",&B)
	dfs([]byte(A),[]byte(B),0)
	fmt.Println(count)
}
//深度优先超时
func dfs (a,b []byte,i int){
	if i == len(b){
		if strings.Contains(string(a),string(b)){
			count++
		}
		return
	}
	if strings.Contains(string(a), string(b[:i+1])){
		dfs(a,b,i+1)
	}else{
		if b[i] == '?'{
			b[i] = '0'
			dfs(a,b,i+1)
			b[i] = '1'
			dfs(a,b,i+1)
			b[i] = '?'
		}
	}
}

深度优先实行递归，

案例

1101010101111010101011111111110001010101
???????????????????????????????????
显示超时

发表于 2022-03-25 11:13:51 回复(0)

没脑子的家伙

package main

import "fmt"

func stringMatch(a, b string) int {
	ret := 0
	at := []rune(a)
	bt := []rune(b)
	res := make(map[string]struct{})
	for i := 0; i < len(at)-len(bt)+1; i++ {
		tmp := 0
		for j := 0; j < len(bt); j++ {
			if at[i+j] == bt[j] || bt[j] == '?' {
				tmp++
				if tmp == len(b) {
					res[a[i:i+len(b)]] = struct{}{}
				}
			}
		}
	}
	ret = len(res)
	return ret
}

func main() {
	a := ""
	fmt.Scan(&a)
	b := ""
	fmt.Scan(&b)
	ret := stringMatch(a, b)
	fmt.Println(ret)
}

发表于 2021-11-22 17:51:24 回复(0)