公式

B - LOOKUP 解説 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文 と呼ばれ、 vectorset などのデータ構造の中身を全て調べるのに便利な記法です。

この問題に対するより短い実装を以下に示します。
実装例(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-tls.size()-t.size() に書き換えると不正解になります。 C++ の string 型の .size() は符号なし整数型を返すので、そのままでは値が負になる演算を正しく行うことができません。)

投稿日時:
最終更新: