I am solving this problem on codeforces : https://codeforces.com/contest/1492/problem/C

My code:

#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;
}

My logic: For each character in t , I am finding the maximum and minimum valid indexes in s which are possible to be taken. Consider this example:

s-->"aaaabbbbbc"
t-->"aabc"

so my vector would be [(0,0) , (1,3) , (4,8) ,(9,9)]

However my code is failing in certain cases. Can someone point out the mistake?

CodePudding user response：

Your code doesn't seem to be implementing your algorithm. In the loop you have

      vec.push_back({i,i});
      vec.push_back({i q-p,j});

So the resulting vector would be alternating pairs of equal indexes and (potentially) different indexes. But:

[(0,0) , (1,3) , (4,8) ,(9,9)]

The (4, 8) pair can't be produced by {i, i}. Further the first pair in your example doesn't fit your stated algorithm either, the first a can be (0, 2).

Your code also seems to assume the letters in the strings are sorted. But what about this input?

s = "aaabbbaaabbbccc";
t = "abc";

You would only match a with the first triplet of as and b with the first triplet of bs and break down on the c completely.