Official
B - LOOKUP Editorial by physics0523
制約が \(|S|,|T| \le 100\) と小さいので、以下の解法が成立します。
- \(S\) の(連続する)部分文字列であって、長さが \(|T|\) であるようなものを全て列挙する。
- 列挙された部分文字列の中に \(T\) と等しいものがあれば
Yes
、そうでなければNo
と出力する。
\(S\) の(連続する)部分文字列であって、長さが \(|T|\) であるようなものを全て列挙する方法は以下の通りです。
- 各先頭位置 \(i=1,2,\dots,|S|-|T|+1\) について、文字列の \(i\) 文字目から \(i+|T|-1\) 文字目までを抜き出す。
但し、 \(|S| < |T|\) となる場合は答えは必ず No
です。
これをコードに起こすと、以下のようになります。
実装例(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;
}
なお、 for(auto &nx : s_sub){}
のような記法は 範囲for文 と呼ばれ、 vector
や set
などのデータ構造の中身を全て調べるのに便利な記法です。
この問題に対するより短い実装を以下に示します。
実装例(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;
}
(メモ: 9行目 sl-tl
を s.size()-t.size()
に書き換えると不正解になります。 C++ の string
型の .size()
は符号なし整数型を返すので、そのままでは値が負になる演算を正しく行うことができません。)
posted:
last update: