AtCoder Beginner Contest 177 B Problem "Substring" Explanation (Python3, C ++, Java)

Hi everyone (who after the contest Good evening!) Is Rute!

AtCoder Beginner Contest 177 B Problem </ b> is about to begin! You can see the explanation of problems A and C from the links below, so please check! !!

Explanation of each problem

A problem B problem C problem
in preparation This article in preparation

Problem summary

Rewrite some characters in $ S $ so that the string $ T $ becomes a substring </ b> of $ S $. At least how many characters will need to be rewritten. The substring </ b> here refers to a continuous substring. Example) 'xxx'is a substring of'yxxxy', but not a substring of 'xxyxx'. </ font>

Problem URL: https://atcoder.jp/contests/abc177/tasks/abc177_b

Constraint

・ $ S $ and $ T $ are $ 1 $ or more and $ 1000 $ or less ・ The length of $ T $ is less than or equal to the length of $ S $ ・ $ S and T $ contain only lowercase letters

Commentary

Gets the substring of $ S $ that is the same length as the string $ T . The number of substrings is(|S|-|T|+1$)Will be pieces(here,|S|IsSRefers to the length of)

For these strings, find out how many characters match the $ T $ string.

|T|The number of matching characters is subtracted from this in this substring"Number of characters that need to be rewritten"It will be. You can find the minimum value of this. (That is, (|T| - (Maximum number of matching strings)) Will be the final answer)

Below are examples of answers in each language (Python3.C ++, Java). (As of 22:26: Java answer example has not been created, so Python3, Java solution example is shown)

Example of answer for each language

Example solution in 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)
  • In Python, you can extract the substring of start index to end index </ b> in character string withcharacter string [start index: end index + 1].
Example solution in C ++

{ABC177B.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  string t;
  //String s,receive t
  cin >> s >> t;
  vector<string> ls(s.size()-t.size()+1);
  // |s|-|t| +Create a string array of size 1.
  //Enumerate the substrings and insert them into the array ls
  for (int i = 0; i < s.size()-t.size()+1; i++){
    ls.at(i) = s.substr(i,t.size());
  }
  int now = 0; //Number of same characters
  int minimum = t.size(); //Answer to output
  for (int i = 0; i < s.size()-t.size()+1; i++){
    now = 0; //Initialization
    for (int j = 0; j < t.size(); j++){
      if (t.at(j) == ls.at(i).at(j)){
        now++;
      }
    }
    if (t.size() - now < minimum){
      // |t| -Update if now is less than minimum
      minimum = t.size() - now;
    }
  }
  //Output minimum
  cout << minimum << endl;
}
Java answer example

in preparation

This is a problem of character string processing, but the following problem applies to the latest B problem.

ABC172B Minor Change ★ The problem is similar to this one </ b> ABC159B String Palindrome Question i of character string processing, but I think it is a little difficult. ABC152B Comparing Strings ★ Difficulty 11 and the simple category of string processing problems. Let's take this opportunity to solve it.

This concludes the explanation of the B problem </ b>. Next is the explanation of the C problem </ b>! !!

Recommended Posts