题目描述
有两个仅包含大写英文字母的字符串 𝑆,𝑇S,T,且字符串 𝑇T 是 𝑆S 的一个子串。
但由于字符串 𝑆S 字迹模糊不清,其某些位置上的字符没有办法进行辨认,这些模糊的位置,用 ?
代替,我们将这个字符串称为 𝑆′S′。
现给定字符串 𝑆′,𝑇S′,T,请你求出,满足条件的所有可能的原字符串 𝑆S 中,字典序最小的一个。
输入格式
输入共两行:
第一行,一个字符串表示 𝑆′S′
第二行,一个字符串表示 𝑇T
输出格式
输出共一行,一个字符串表示答案
数据范围
设 ∣𝑆∣,∣𝑇∣∣S∣,∣T∣ 分别为字符串 𝑆,𝑇S,T 的长度
- 对于 30%30%的数据,1≤∣𝑇∣≤∣𝑆∣≤101≤∣T∣≤∣S∣≤10
- 对于 60%60%的数据,1≤∣𝑇∣≤∣𝑆∣≤1021≤∣T∣≤∣S∣≤102
- 对于 100%100%的数据,1≤∣𝑇∣≤∣𝑆∣≤1041≤∣T∣≤∣S∣≤104
数据保证存在字符串 𝑆S 满足条件
样例数据
输入:
?AI?
IAI
输出:
IAIA
#include <bits/stdc++.h>
using namespace std;
string s;
string t;
int lens;
int lent;
string ans;
bool pipei(int x)
{
for (int j=0;j<lent;j++)
{
if (t[j]!=s[x+j]&&s[x+j]!='?')
{
return false;
}
}
return true;
}
int main()
{
cin>>s>>t;
lens=s.size();
lent=t.size();
ans=s;
for (int i=0;i<lens;i++)
{
if (ans[i]=='?'){
ans[i]='Z';
}
}
for (int i=lens-lent;i>=0;i--)
{
if (pipei(i))
{
string s1=s;
for (int j=0;j<lent;j++)
{
s1[i+j]=t[j];
}
for (int i=0;i<lens;i++)
{
if (s1[i]=='?')
{
s1[i]='A';
}
}
if (ans>s1)
{
ans=s1;
}
}
}
cout<<ans;
return 0;
}
详见代码: