AtCoder-Anfängerwettbewerb 177 B Problem "Teilzeichenfolge" Erläuterung (Python3, C ++, Java)

Hallo allerseits (wer nach dem Wettbewerb Guten Abend!) Ist Rute!

AtCoder-Anfängerwettbewerb 177 B Problem </ b> beginnt gleich! Die Erklärung der Probleme A und C finden Sie unter den folgenden Links. Überprüfen Sie dies bitte! !!

Erklärung jedes Problems

Ein Problem B Problem C Problem
in Vorbereitung Dieser Beitrag in Vorbereitung

Problemzusammenfassung

Schreiben Sie einige Zeichen in $ S $ neu, sodass die Zeichenfolge $ T $ zu einem Teilstring </ b> von $ S $ wird. Zumindest wie viele Zeichen müssen neu geschrieben werden. Der Teilstring </ b> bezieht sich hier auf einen kontinuierlichen Teilstring. Beispiel) "xxx" ist ein Teilstring von "yxxxy", aber kein Teilstring von "xxyxx". </ font>

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

Zwang

・ $ S $, $ T $ ist $ 1 $ oder mehr und $ 1000 $ oder weniger ・ Die Länge von $ T $ ist kleiner als die Länge von $ S $ ・ $ S und T $ enthalten nur Kleinbuchstaben

Kommentar

Ruft den Teilstring von $ S $ ab, der dieselbe Länge wie der Teilstring $ T $ hat. Die Anzahl der Teilzeichenfolgen(|S|-|T|+1)Wird Stücke sein(Hier,|S|IstSBezieht sich auf die Länge von)

Finden Sie für diese Zeichenfolgen heraus, wie viele Zeichen mit der Zeichenfolge $ T $ übereinstimmen.

|T|Die Anzahl der übereinstimmenden Zeichen wird in diesem Teilstring davon abgezogen"Anzahl der Zeichen, die neu geschrieben werden müssen"Es wird sein. Den Mindestwert finden Sie hierfür. (Das ist, (|T| - (Maximale Anzahl übereinstimmender Zeichenfolgen)) Wird die endgültige Antwort sein)

Nachfolgend finden Sie Beispiele für Antworten in jeder Sprache (Python 3.C ++, Java). (Stand 22:26: Java-Antwortbeispiel wurde nicht erstellt, daher werde ich ein Antwortbeispiel in Python3, Java zeigen.)

Beispiel für eine Antwort für jede Sprache

Beispiellösung 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 können Sie die Teilzeichenfolge von Startindex bis Endindex </ b> in Zeichenfolge mit Zeichenfolge [Startindex: Endindex + 1] extrahieren.
Lösungsbeispiel in C ++

{ABC177B.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  string t;
  //String s,empfange t
  cin >> s >> t;
  vector<string> ls(s.size()-t.size()+1);
  // |s|-|t| +Erstellen Sie ein String-Array der Größe 1.
  //Zählen Sie Teilzeichenfolgen auf und fügen Sie sie in das Array ls ein
  for (int i = 0; i < s.size()-t.size()+1; i++){
    ls.at(i) = s.substr(i,t.size());
  }
  int now = 0; //Anzahl der gleichen Zeichen
  int minimum = t.size(); //Antwort auf Ausgabe
  for (int i = 0; i < s.size()-t.size()+1; i++){
    now = 0; //Initialisieren
    for (int j = 0; j < t.size(); j++){
      if (t.at(j) == ls.at(i).at(j)){
        now++;
      }
    }
    if (t.size() - now < minimum){
      // |t| -Aktualisieren, wenn jetzt weniger als das Minimum ist
      minimum = t.size() - now;
    }
  }
  //Ausgangsminimum
  cout << minimum << endl;
}
Java-Antwortbeispiel

in Vorbereitung

Dies ist ein Problem der Zeichenfolgenverarbeitung, aber das folgende Problem gilt für das neueste B-Problem.

ABC172B Minor Change ★ Das Problem ähnelt diesem </ b> ABC159B String Palindrome Frage i zur Verarbeitung von Zeichenketten, aber ich denke, es ist ein wenig schwierig. ABC152B Comparing Strings ★ Schwierigkeitsgrad 11 ist eine einfache Kategorie unter den Problemen bei der Zeichenfolgenverarbeitung. Lassen Sie uns diese Gelegenheit nutzen, um es zu lösen.

Dies schließt die Erklärung des B-Problems </ b> ab. Als nächstes folgt die Erklärung des C-Problems </ b>! !!

Recommended Posts