Codeforces 1492C题代码逻辑部分测试用例失败原因求助

问题场景 #

我在Codeforces平台求解编号1492C的题目时，提交的代码无法通过全部测试用例。

提交代码 #

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    
      int n,m;
      cin>>n>>m;
      string str1,str2;
      cin>>str1;
      cin>>str2;
      
      int i=0;
      int p=0;
      vector<pair<int,int>>vec;
      while(i<n && p<m)
      {
          int j=i;
          int q=p;
          while(j<n-1 && str1[j+1]==str1[i])
          j++;
          while(q<m-1 && str2[q+1]==str2[p])
          q++;
          
          vec.push_back({i,i});
          vec.push_back({i+q-p,j});
          
          i=j+1;
          p=q+1;
      }
      int maxi=1;
      for(int i=0;i<vec.size()-1;i++)
      {
          maxi=max(maxi,vec[i+1].second-vec[i].first);
      }
    cout<<maxi<<endl;
    return 0;
}

原有设计思路 #

对于字符串t（对应代码中str2）的每个字符，我尝试找到其在字符串s（对应代码中str1）中可选取的最小、最大合法匹配下标。
测试示例：当s为"aaaabbbbbc"、t为"aabc"时，代码生成的存储下标对的vector为[(0,0) , (1,3) , (4,8) ,(9,9)]。

核心逻辑问题 #

• 分块匹配的前提完全错误。代码默认将s和t中连续相同字符做整块绑定匹配，这个假设不成立。举个反例：当s为"aaabaaa"、t为"aaaa"时，代码会先识别s中起始的3个连续a为一个块，t中4个连续a为一个块，计算得到的第二个pair为(0+3, 2)也就是(3,2)，出现左边界大于右边界的非法值，直接导致结果错误。
• 下标计算没有合法性校验。代码中用i+q-p计算匹配位置左边界的逻辑毫无依据，既没有校验对应位置的字符是否匹配，也没有保证匹配位置严格递增，完全不符合子序列匹配的规则。
• 上下标数组的构建方法完全错误。要得到t中每个字符在s中匹配的最左、最右下标，根本不需要做连续字符分块，正确流程是：
  1. 从左到右线性扫描两个字符串，构建l数组：l[k]表示t的第k个字符在s中能匹配到的最左下标，满足s[l[k]] == t[k]且l[k] > l[k-1]
  2. 从右到左线性扫描两个字符串，构建r数组：r[k]表示t的第k个字符在s中能匹配到的最右下标，满足s[r[k]] == t[k]且r[k] < r[k+1]
  3. 遍历所有相邻的匹配位置，计算r[k] - l[k-1]的最大值，就是题目要求的结果
• 边界处理存在漏洞。循环终止条件设为i<n && p<m，当两个字符串的连续块数量不匹配时，生成的vec长度不足，后续遍历计算最大值时会出现遗漏匹配对、甚至计算逻辑完全失效的问题。

内容的提问来源于stack exchange，提问作者Vatsal A Mehta