Zählen Sie die Anzahl der Teilzeichenfolgen der Länge M, die genau K-mal in einer Zeichenfolge vorkommen

In diesem Artikel befassen wir uns mit einem einzigartigen und faszinierenden Problem im Bereich der Informatik – „Zähle Teilstrings der Länge M, die genau K-mal in einem String vorkommen“. Diese Art von Fragen wird häufig bei Programmierwettbewerben und Interviews gestellt. Bevor wir beginnen, definieren wir, womit wir es zu tun haben -

• Substring− Eine zusammenhängende Sequenz, die innerhalb einer anderen Zeichenfolge gefunden wird.

• M-Länge− Die Länge des Teilstrings, an dem wir interessiert sind.

• K mal − Die genaue Häufigkeit, mit der die Teilzeichenfolge in der Originalzeichenfolge vorkommen sollte.

Algorithmusbeschreibung

Um dieses Problem zu lösen, nutzen wir die Leistungsfähigkeit von Hash-Maps (in C++ auch ungeordnete Maps genannt). Mit Hash-Maps können wir Daten in Form von Schlüssel-Wert-Paaren speichern und eine konstante Zeitkomplexität für Such- und Einfügevorgänge bereitstellen, was sie zu einem hervorragenden Werkzeug zur Lösung solcher Probleme macht.

Der Algorithmus zur Berechnung des M-langen Teilstrings, der genau K-mal in einem String vorkommt, lautet wie folgt -

• Initialisieren Sie eine leere Hash-Map.

• Durchlaufen Sie die Zeichenfolge und erstellen Sie alle möglichen Teilzeichenfolgen der Länge M.

• Fügen Sie jeden Teilstring zur Hash-Map hinzu. Wenn es bereits vorhanden ist, erhöhen Sie seine Anzahl.

• Nachdem alle Teilzeichenfolgen berechnet wurden, iterieren Sie über die Hash-Map, um alle Teilzeichenfolgen zu finden, die genau K-mal vorkommen.

C++-Implementierung

Dies ist eine C++-Implementierung des oben genannten Algorithmus -

Beispiel

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map<string, int> count_map;
   int n = s.length();
   
   for (int i = 0; i <= n - M; i++) {
      string substring = s.substr(i, M);
      count_map[substring]++;
   }
   
   int count = 0;
   for (auto it : count_map) {
      if (it.second == K)
         count++;
   }

    return count;
}

int main() {
   string s = "abcabcabc";
   int M = 3;
   int K = 3;
   
   int result = countSubstrings(s, M, K);
   cout << "The number of M-length substrings occurring exactly K times is: " << result << endl;
   
   return 0;
}

Ausgabe

The number of M-length substrings occurring exactly K times is: 1

Im obigen Code verwendet die Funktion countSubstrings die Eingabezeichenfolge s, die Länge der Teilzeichenfolge M und die Anzahl der Vorkommen K als Parameter. Es initialisiert eine ungeordnete Map count_map, um alle Teilzeichenfolgen und deren Vorkommen zu verfolgen. Anschließend wird die Zeichenfolge durchlaufen, um alle möglichen Teilzeichenfolgen der Länge M zu erstellen, und für jede Teilzeichenfolge wird die Anzahl in der Karte erhöht. Sobald alle Teilzeichenfolgen berechnet wurden, wird die Karte durchlaufen, um alle Teilzeichenfolgen zu zählen, die genau K-mal vorkommen.

Die Hauptfunktion ist der Ort, an dem die Codeausführung beginnt. Es initialisiert die Zeichenfolge s und die Werte von M und K. Rufen Sie dann die Funktion countSubstrings auf und drucken Sie das Ergebnis aus.

Testfallbeispiel

Betrachten wir die Zeichenfolge „abcabcabc“, wobei M=3 und K=3.

Hier sind die Teilzeichenfolgen der M-Länge „abc“, „bca“, „cab“, „abc“, „bca“, „cab“, „abc“. Offensichtlich kommt die Teilzeichenfolge „abc“ in der Zeichenfolge genau dreimal vor, sodass die Ausgabe des Programms 1 ist.

Diese Herangehensweise an das Problem, bei der wir eine Hash-Map zur Berechnung von Teilzeichenfolgen verwenden, ist ein gutes Beispiel für den Raum-Zeit-Kompromiss in der Informatik. Wenn wir zusätzlichen Speicherplatz zum Speichern von Teilzeichenfolgen und deren Anzahl verwenden, können wir die zeitliche Komplexität des Problems erheblich reduzieren, indem wir Vorkommen in konstanter Zeit zählen.

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität dieses Algorithmus beträgt O(n), wobei n die Länge der Zeichenfolge ist. Dies liegt daran, dass wir die Zeichenfolge nur einmal durchlaufen, um alle möglichen Teilzeichenfolgen der Länge M zu erstellen.

Aufgrund des Speicherbedarfs der Hash-Map beträgt die Platzkomplexität auch O(n), im schlimmsten Fall ist jeder Teilstring eindeutig, was zu n verschiedenen Einträgen in der Karte führt.

Fazit

In diesem Artikel untersuchen wir ein häufiges Problem in der Informatik – das Zählen der Anzahl von Teilstrings der M-Länge, die genau K-mal in einem String vorkommen. Wir haben eine effiziente Lösung in C++ mithilfe von Hash-Maps implementiert, die uns zeitkonstante Such- und Einfügungsvorgänge ermöglicht. Dieses Problem ist ein perfektes Beispiel dafür, wie Datenstrukturen und Algorithmen gemeinsam verwendet werden können, um komplexe Probleme effektiv zu lösen.

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der Teilzeichenfolgen der Länge M, die genau K-mal in einer Zeichenfolge vorkommen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!