Contest Duration: - (local time) (100 minutes) Back to Home
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: