AtCoder Beginner Contest 177 B問題「Substring」解説(Python3,C++,Java)

皆さんこんにちは(コンテスト後の方はこんばんは！)Ruteです！

AtCoder Beginner Contest 177 B問題の解説をこれから始めます！
A問題,C問題の解説は以下のリンクより見ることが出来ますのでご確認下さい！！

各問題の解説

A問題	B問題	C問題
準備中です	この記事です	準備中です

問題概要

文字列$T$が$S$の部分文字列となるように、$S$のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要があるでしょう。
ここでの部分文字列は連続する部分列のことを指します。
例) 'xxx'は'yxxxy'の部分文字列であるが、'xxyxx'の部分文字列ではない。

問題URL : https://atcoder.jp/contests/abc177/tasks/abc177_b

制約

・$S$,$T$は$1$文字以上$1000$文字以下
・$T$の長さは$S$の長さ以下
・$S,T$は英小文字のみを含む

解説

$S$の部分文字列のうち、文字列$T$と同じ長さの部分文字列を取得します。
部分文字列の個数は($|S|-|T|+1$)個となります(ここで、$|S|$は$S$の長さを指します)

これらの文字列について、$T$の文字列と一致している文字数を調べます。

$|T|$から一致している文字数のを引いたものがこの部分文字列における「書き換える必要がある文字数」となります。これの最小値を求めれば良いです。
(つまり、
($|T|$ - (一致している文字列の最大数))
が最終的な答えになります)

以下、各言語(Python3.C++,Java)での解答例を示します。
(22:26時点 : Javaの解答例が出来ていないので、Python3,Javaでの解答例を示します)

各言語解答例

Python3での解答例

ABC177B.py

s = input()
t = input()
ls = []
for i in range(len(s) - len(t) + 1):
    ls.append(s[i:i+len(t)])
now = 0
minimum = len(t)
for i in range(len(ls)):
    now = 0
    for j in range(len(t)):
        if t[j] == ls[i][j]:
            now += 1
    if len(t) - now < minimum:
        minimum = len(t) - now
print(minimum)

※Pythonでは文字列[開始インデックス:終了インデックス+1]で文字列における開始インデックスから終了インデックスまでの部分文字列を取り出すことが出来ます

C++での解答例

ABC177B.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  string t;
  //文字列s,tを受け取ります
  cin >> s >> t;
  vector<string> ls(s.size()-t.size()+1);
  // |s|-|t| + 1のサイズのstring配列を作成します。
  //部分文字列を列挙し配列lsに挿入します
  for (int i = 0; i < s.size()-t.size()+1; i++){
    ls.at(i) = s.substr(i,t.size());
  }
  int now = 0; //同じ文字の数
  int minimum = t.size(); //出力する答え
  for (int i = 0; i < s.size()-t.size()+1; i++){
    now = 0; //初期化
    for (int j = 0; j < t.size(); j++){
      if (t.at(j) == ls.at(i).at(j)){
        now++;
      }
    }
    if (t.size() - now < minimum){
      // |t| - now がminimumより小さかったら更新する
      minimum = t.size() - now;
    }
  }
  // minimumを出力する
  cout << minimum << endl;
}

Javaでの解答例

準備中

このような文字列処理の問題ですが、直近のB問題だと以下の問題があてはまります。

ABC172B Minor Change　★今回の問題と類似した問題です
ABC159B String Palindrome　文字列処理の問iですが、若干難易度が高いと思います
ABC152B Comparing Strings
★Difficulty11と、文字列処理の問題の中では簡単な部類です。この機会に解いてみましょう。

以上で、B問題の解説を終わります。次はC問題の解説です！！