题解 AT3600 【[ABC076C] Dubious Document 2】
TRZ_2007
2020-08-27 13:34:10
**[题解 AT3600 【[ABC076C] Dubious Document 2】](https://www.luogu.com.cn/problem/AT3600)**
由于 AtCoder 的端口炸了，所以这份代码是在 AtCoder 上直接提交的，记录详情：
# Solution
如果这道题目的字符串长度加强一下那这题会变得十分恐怖，但是由于长度都**小于等于50**，所以我们可以考虑**暴力**。
**怎么暴力呢？** 我们枚举每一个配对情况，看一下是否可以配对，如果可以就看一下是否可以更新答案，最后输出即可。
看不懂上面文字的（~~应该都看得懂吧~~）我们来看一下这一堆图来加强理解：
我们以第一组样例为例
我们发现目标串的对应位置是一个未知元素，因此可以和我们的字符``c``匹配成功，于是指针``j``后移一位。
我们发现目标串中是已知元素``t``，不能与``o``进行匹配，所以匹配失败。指针``i``向后移一位，指针``j``复原。
（一下省略 infinity 张图……）
所以这就是这道题暴力的算法，还是比较简单的，觉得评个黄题是不是过了，给个橙差不多……
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
string ans = "";
string s,t,tmp = "";
int ls,lt,flag;
int main() {
cin >> s >> t;
ls = s.size();lt = t.size();
if(ls < lt) { //如果子串比目标串都长，那么肯定失配
puts("UNRESTORABLE");
return 0;
}
for(int i = 0;i < ls - lt + 1;i++) {
tmp = s;flag = 0; //用tmp代替目标串
for(int j = i;j < i + lt;j++) {
if(tmp[j] == '?') tmp[j] = t[j - i]; //如果是未知元素，那么匹配
else {
if(tmp[j] != t[j - i]) { //如果不是未知元素且不相等，那么失配
flag = 1;
break;
}
}
}
// cout << tmp << "\n";
if(flag == 0) {
for(int j = 0;j < ls;j++) { //对于没有匹配到的未知元素附以字典序最小的a
if(tmp[j] == '?') tmp[j] = 'a';
}
if(ans == "") ans = tmp;
else ans = min(ans,tmp);
}
}
if(ans != "") cout << ans << "\n";
else puts("UNRESTORABLE");
return 0;
}
```