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, printNo
.
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: