AtCoder Beginner Contest 177 B Explication du problème "Sous-chaîne" (Python3, C ++, Java)

Salut à tous (qui après le concours Bonsoir!) C'est Rute!

Concours pour débutants AtCoder 177 B Le problème </ b> est sur le point de commencer! Vous pouvez voir l'explication des problèmes A et C à partir des liens ci-dessous, veuillez donc vérifier! !!

Explication de chaque problème

Un problème Problème B Problème C
en préparation Cet article en préparation

Résumé du problème

Réécrivez certains caractères dans $ S $ pour que la chaîne $ T $ devienne une sous-chaîne </ b> de $ S $. Au moins combien de caractères devront être réécrits. La sous-chaîne </ b> fait ici référence à une sous-chaîne continue. Exemple) 'xxx' est une sous-chaîne de'yxxxy', mais pas une sous-chaîne de xxyxx'`. </ font>

URL du problème: https://atcoder.jp/contests/abc177/tasks/abc177_b

Contrainte

・ $ S $, $ T $ est de 1 $ ou plus et de 1000 $ ou moins ・ La longueur de $ T $ est inférieure ou égale à la longueur de $ S $ ・ $ S et T $ n'incluent que des lettres minuscules

Commentaire

Obtient la sous-chaîne de $ S $ qui a la même longueur que la sous-chaîne $ T . Le nombre de sous-chaînes(|S|-|T|+1$)Seront des morceaux(ici,|S|EstSSe réfère à la longueur de)

Pour ces chaînes, découvrez combien de caractères correspondent à la chaîne $ T $.

|T|Le nombre de caractères correspondants en est soustrait dans cette sous-chaîne"Nombre de caractères à réécrire"Ce sera. Vous pouvez trouver la valeur minimale de ceci. (C'est, (|T| - (Nombre maximum de chaînes correspondantes)) Sera la réponse finale)

Vous trouverez ci-dessous des exemples de réponses dans chaque langage (Python 3.C ++, Java). (À partir de 22:26: l'exemple de réponse Java n'a pas été créé, je vais donc montrer un exemple de réponse en Python3, Java)

Exemple de réponse pour chaque langue

Exemple de solution en 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)
  • En Python, vous pouvez extraire la sous-chaîne de index de début à index de fin </ b> dans chaîne de caractères avec chaîne de caractères [index de début: index de fin + 1].
Exemple de solution en C ++

{ABC177B.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  string t;
  //Chaîne s,recevoir t
  cin >> s >> t;
  vector<string> ls(s.size()-t.size()+1);
  // |s|-|t| +Créez un tableau de chaînes de taille 1.
  //Énumérer les sous-chaînes et insérer dans le tableau ls
  for (int i = 0; i < s.size()-t.size()+1; i++){
    ls.at(i) = s.substr(i,t.size());
  }
  int now = 0; //Nombre de mêmes caractères
  int minimum = t.size(); //Réponse à la sortie
  for (int i = 0; i < s.size()-t.size()+1; i++){
    now = 0; //Initialisation
    for (int j = 0; j < t.size(); j++){
      if (t.at(j) == ls.at(i).at(j)){
        now++;
      }
    }
    if (t.size() - now < minimum){
      // |t| -Mettre à jour si maintenant est inférieur au minimum
      minimum = t.size() - now;
    }
  }
  //Sortie minimum
  cout << minimum << endl;
}
Exemple de réponse Java

en préparation

Bien qu'il s'agisse d'un tel problème de traitement de chaîne de caractères, le problème suivant s'applique au dernier problème B.

ABC172B Changement mineur ★ Le problème est similaire à celui-ci </ b> ABC159B String Palindrome Question i du traitement des chaînes de caractères, mais je pense que c'est un peu difficile. ABC152B Comparing Strings ★ La difficulté 11 est une catégorie simple parmi les problèmes de traitement des chaînes. Profitons de cette occasion pour le résoudre.

Ceci conclut l'explication du problème B </ b>. Vient ensuite l'explication du problème C </ b>! !!

Recommended Posts