Official

B - LOOKUP Editorial by en_translator


Since the constraints is as small as \(|S|,|T| \le 100\), the following solution is valid:

  • Enumerate all (consecutive) substrings of \(S\), of length \(|T|\).
  • If one of them equals \(T\), print Yes; otherwise, print No.

One can enumerate all (consecutive) substrings of \(S\), of length \(|T|\), as follows:

  • for each initial position \(i=1,2,\dots,|S|-|T|+1\), extract from \(i\)-th through \((i+|T|-1)\)-th character of the string.

Here, if \(|S| < |T|\), then the answer is always No.
This algorithm can be written as a code as follows:
Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s,t;
  cin >> s >> t;
  int sl=s.size(),tl=t.size();
  if(sl<tl){
    cout << "No\n";
    return 0;
  }
  vector<string> s_sub;
  for(int i=0;i<sl-tl+1;i++){
    string cur;
    for(int j=0;j<tl;j++){
      cur.push_back(s[i+j]);
    }
    s_sub.push_back(cur);
  }
  for(auto &nx : s_sub){
    if(nx==t){
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}

Note the notation for(auto &nx : s_sub){}, which is called the extended for statement, which is useful when enumerate all elements of a vector or set.

The following is a simpler implementation. Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s,t;
  cin >> s >> t;
  int sl=s.size(),tl=t.size();
  for(int i=0;i<=sl-tl;i++){
    string cur;
    for(int j=0;j<tl;j++){
      cur.push_back(s[i+j]);
    }
    if(cur==t){
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}

(Note: replacing sl-tl in the 9-th line with s.size()-t.size() results in a wrong answer. Since the .size() function of a string type returns an unsigned integer type, you cannot directly perform an operation that results in a negative value.)

posted:
last update: