UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)-D - Match or Not

Solost

2023 年 01 月 29 日

198 次浏览

暂无评论

1571字数

题目题解

![请输入图片描述](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/211866676.png)

## solution

这道题卡了好久，题目意思看了好久没看懂。题目大意是有两个字符串s,t，s的长度大于t,每次删去s比t长的那部分，从开始删除，删到结束，每次删除多的，如果每个字符都相同输出yes，否则no。

1. 这道题的解法刚开始是想办法把字符串截断再拼接，发现每次都需要复制字符串，以为时间复杂度在这个地方比较高。
2. 后来优化成`s.erase(i, l)`这个东西是把从i开始长度是l的字符删去，然后来正常匹配，我想这个复杂度主要取决于erase的实现原理，后来看了时间，和自己手写的差不多hehe。
3. 再后来发现主要是常数问题，每次修改后都需要判断一次是不是匹配，如果字符串特别长那么就把同一个地方比较好多次，所以后来优化了一点常数，把不匹配的地方拿出来专门来测试，发现虽然快了点，但是还是超时。
4. 最后就没办法了，比赛的时候没写出来真烦，他们都写出来了！！！这道题的解法我们可以分析一下，每次删除长度为l的字符串从头到尾，我们就可以发现，有一部分是匹配的，有一部分是不匹配的，两边匹配，中间不匹配时可以删去的。我们定义最长公共前缀是l,最长公共后缀是r,那么x是删除的地方，`x >= 0 && x < t.size()`，我们需要把那些中间不匹配的地方删除了，删除掉一点前后缀都是可以的，则这样就是匹配的。匹配的情况是`x <= l && x >= l - r`
   ```C++
   #include<map>
   #include<set>
   #include<stack>
   #include<queue>
   #include<cmath>
   #include<vector>
   #include<bitset>
   #include<cstdio>
   #include<cstring>
   #include<fstream>
   #include<cstdlib>
   #include<iostream>
   #include<algorithm>
   #include<unordered_map>

using namespace std;
   #define endl '\n'
   #define IOS                       \
       ios_base::sync_with_stdio(0); \
       cin.tie(0);                   \
       cout.tie(0);
   typedef long long ll;
   typedef pair<int,int> PII;
   typedef unsigned long long ull;
   const int INF = 0x3f3f3f3f, mod = 1000000007;
   const int N = 2e5 + 10;
   int l, r;
   bool check(char a, char b){
       return a == '?' || b == '?' || a == b;
   }
   int main(){
       string s, t;
       cin >> s >> t;
       int n1 = s.size(), n2 = t.size();
       while(l < n2 && check(s[l], t[l])) l++;
       while(r < n2 && check(s[n1 - r - 1], t[n2 - r - 1])) r++;
       for(int i = 0; i <= n2; i++){
           if(i <= l && i >= n2 - r)
               puts("Yes");
           else
               puts("No");
       }
       return 0;
   }
   ```

最后修改：2023 年 02 月 02 日