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;
}
