[14]字符串匹配-百度2018秋

1.题目描述

牛牛有两个字符串 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'和'?'。
• 输出描述:
  输出一个整数,表示能完成匹配的字符串种数。
• 输入示例:

  00010001
  ??
  

• 输出示例:

  3
  

2.题目解析

将A从前到后依次遍历与B比较，遇到'?'特殊处理即可。使用穷举法。

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main() {
  string A;
  cin >> A;
  string B;
  cin >> B;
  
  set<string> resset;
  for(int i=0;i<A.size()-B.size()+1;++i){
      string res;
      int now = i;
      for(int j=0;j<B.size();++j){
          if(B[j] == '?'){
              res.append(1,A[now]);
              ++now;
          }else if(B[j] == A[now]){
              res.append(1,A[now]);
              ++now;
          }else{
              break;
          }
      }
      if(res.size() == B.size()){
          resset.insert(res);
      }
  }
  printf("%d\n",resset.size());
  return 0;
}

其他参考答案

#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B;
  cin >> A >> B;
  int ans = 0; 
  set<string> s;
  for(int i=0;i!= A.size();++i) {// 遍历字符串A
    // 剩余的长度不够与B比较
    if(A.size()-i < B.size()) break;
    int pos = i;
    int flag = true;//标识匹配是否成功
    for(int j=0;j!=B.size();++j){
        if(A[pos] == B[j] || B[j] == '?'){
            pos++;// 比较下一个字符
        }else{
            flag = false;
            break;// 停止比较
        }
    }
    if(flag){
        s.insert(A.substr(i,B.size()));
    }
  }
  cout << s.size() << endl;
  return 0;
}

先切割字符串，存储效率更高。

#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B;
  cin >> A >> B;
  int ans = 0; 
  set<string> s;
  for(int i = 0; i != A.size(); ++i) {// 遍历字符串A
    // 切出子串
    int j = i + B.size() - 1;
    if(j >= A.size()) continue;
    string cur = A.substr(i, j - i + 1);
    if(s.count(cur)) continue;
    s.insert(cur); // 记录子串
    // 把子串与B串比较
    bool flag = true;
    for(int k = 0; k < B.size(); k++) {
      if(cur[k] == B[k]) continue;
      if(B[k] == '?') continue;
      else {
          flag = false;
          break;
      }
    }
    if(flag) ans++; // 计数
  }
  cout << ans << endl;
  return 0;
}

牛客题目