首页 > 试题广场 >

字符串匹配

[编程题]字符串匹配

热度指数：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
??

输出

算法知识视频讲解

Java

blue&&lan

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        HashSet<String> s = new HashSet<>();
        for (int i = 0; i < a.length() - b.length() + 1; i++) {
            int c = 0;
            for (int j = 0, k = i; j < b.length(); j++, k++) {
                if (b.charAt(j) == '?' || b.charAt(j) == a.charAt(k)) {
                    //匹配到b串中的字符个数+1
                    c++;
                }
            }
            //匹配的字符数等于b串长度，说明从第i项开始在a串中完成匹配，将匹配出的存入set
            if (c == b.length()) {
                s.add(a.substring(i, i + b.length()));
            }
        }
        System.out.print(s.size());
    }
}

发表于 2022-03-26 11:53:18 回复(0)

Java

牛客834002708号

不会用正则表达式的也可以直接比较

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String A = in.nextLine();
            String B = in.nextLine();
            LinkedHashSet<String> set = new LinkedHashSet();   // 存储可以正确匹配的字符串，最终的set.size()就是匹配种数
            for(int i=0;i<=A.length()-B.length();i++){
                boolean b = true;
                for(int j=0,index=i;j<B.length();j++,index++){
                    if(B.charAt(j)!='?' && B.charAt(j)!=A.charAt(index)){ // B的字符不是？，且对应的字符不相等，则说明不可以匹配
                        b = false;                          // 标记不可以匹配
                        break;
                    }
                }
                if(b){                                      // 可以匹配，添加匹配子串
                    set.add(A.substring(i,i+B.length()));
                }
            }
            System.out.println(set.size());
        }
    }
}

发表于 2021-09-01 00:31:31 回复(0)