AT3600 题解

Fengxiang008 · 2021-07-14 07:59:31 · 题解

题意：

给定 S，T，2 个字符串，判断 T 字符串是否是 S 的子串，? 可以代替任何字符，如果存在，输出 S 的最小字典序的字符串，否则输出 \texttt{UNRESTORABL}。

思路：

利用 set 自动排序的特性，构造出多个 T 是 S 子串的字符串，然后挑选字典序最小的即可。

（之前我是想用 KMP 算法，直接判断是否存在子串，然后再进行变化，不过事实证明这样的算法可行性太低，但是自身学习了下 KMP 算法也不错）。

代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<map>
#include<set>
using namespace std;
string s, t;
set<string> S;
void Work()
{
    int lens = s.size();
    int lent = t.size();
    for(int i = 0; i < lens; i++)
    {
        if(s[i] == '?' || s[i] == t[0])//如果字符相等
        {
            string tmp = s;              //构造判断子串之前的字符
            for(int j = 0; j < i; j++)
                if(tmp[j] == '?')
                    tmp[j] ='a';    
            bool can = false;
            for(int j = 0; j < lent; j++)    //判断是否为子串
            {

                if(tmp[i+j]!= '?' && tmp[i+j] != t[j])  //字符匹配
                    break;
                tmp[i+j] = t[j];
                if(j == lent - 1) can = true;
            }
            if(can)
            {
                for(int j = i + lent; j < lens; j++) if(tmp[j] == '?') tmp[j] = 'a';//处理匹配后的字符
                S.insert(tmp);  //压入容器
            }
        }
    }
    if(S.size() == 0) cout << "UNRESTORABLE" << endl;
    else cout << *S.begin() << endl;
}
int main()
{
    cin >> s >> t;
    Work();
    return 0;
}