Zählen Sie die Anzahl der Teilzeichenfolgen, die aus einem einzelnen eindeutigen Zeichen bestehen

In diesem Artikel besprechen wir das Problem der Zählung der Anzahl von Teilzeichenfolgen, die aus einzelnen unterschiedlichen Zeichen in einer bestimmten Zeichenfolge bestehen. Wir werden einen effizienten Algorithmus zur Lösung dieses Problems untersuchen und C++-Code zur Implementierung bereitstellen.

Problemstellung

Bei einer gegebenen Zeichenfolge S besteht die Aufgabe darin, die Anzahl der Teilzeichenfolgen zu zählen, die aus einzelnen unterschiedlichen Zeichen bestehen.

Wenn die Eingabezeichenfolge beispielsweise „aaaaa“ lautet, sollte die Ausgabe 15 sein, da es 15 Teilzeichenfolgen gibt, die aus einzelnen unterschiedlichen Zeichen bestehen. Die Teilzeichenfolgen sind „a“, „a“, „a“, „a“, „a“, „a“, „a“, „a“, „a“, „a“, „a“, „aaa“. , „aaa“, „aaaa“, „aaaa“, „aaaa“.

Algorithmus

Wir können dieses Problem mit linearer Zeitkomplexität lösen. Wir können die Eingabezeichenfolge durchlaufen und das aktuelle Zeichen und die Länge der aktuellen Teilzeichenfolge verfolgen. Immer wenn ein neues Zeichen angetroffen wird oder das Ende der Zeichenfolge erreicht ist, können wir die Anzahl der Teilzeichenfolgen zählen, die durch das aktuelle Zeichen gebildet werden können, sowie die Länge der aktuellen Teilzeichenfolge.

Hier ist ein Schritt-für-Schritt-Algorithmus zur Lösung dieses Problems -

• Anzahl initialisieren und auf 1 verlängern.

• Iterieren Sie über String S von Index 1 bis n-1.

• Wenn das aktuelle Zeichen mit dem vorherigen Zeichen übereinstimmt, wird die Länge um 1 erhöht.

• Wenn sich das aktuelle Zeichen vom vorherigen Zeichen unterscheidet, addieren Sie (len*(len+1))/2 zum Zählen und setzen Sie len ​​auf 1 zurück.

• Anzahl der Rücksendungen.

Nehmen wir die Zeichenfolge „aaaaa“ als Beispiel, um den Algorithmus zu verstehen -

• Anzahl initialisieren und auf 1 verlängern.

• Iterieren Sie über eine Zeichenfolge von Index 1 bis n-1:

• Bei Index 1 ist das aktuelle Zeichen dasselbe wie das vorherige Zeichen, daher wird len um 1 erhöht.

• Bei Index 2 ist das aktuelle Zeichen dasselbe wie das vorherige Zeichen, daher wird len um 1 erhöht.

• Bei Index 3 ist das aktuelle Zeichen dasselbe wie das vorherige Zeichen, daher wird len um 1 erhöht.

• Bei Index 4 ist das aktuelle Zeichen dasselbe wie das vorherige Zeichen, daher wird len um 1 erhöht.

• Wir haben das Ende der Zeichenfolge erreicht, also addieren Sie (len*(len+1))/2, um zu zählen. Anzahl = Anzahl + (5*(5+1))/2 = 15.

• Anzahl der Rücksendungen.

C++-Implementierung

Dies ist der C++-Code, der den obigen Algorithmus implementiert -

Beispiel

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

int countSubstrings(string S) {
   int n = S.length();
   int count = 1, len = 1;
   for (int i = 1; i < n; i++) {
      if (S[i] == S[i-1]) {
         len++;
      } else {
         count += (len*(len+1))/2;
         len = 1;
      }
   }
   count += (len*(len+1))/2;
   return count-1;
}

int main() {
   string S = "aaaaa";
   int count = countSubstrings(S);
   cout << count << endl;
   return 0;
}

Ausgabe

15

Fazit

In diesem Artikel haben wir das Problem besprochen, die Anzahl der Teilzeichenfolgen zu zählen, die aus einzelnen unterschiedlichen Zeichen in einer bestimmten Zeichenfolge bestehen. Wir stellen einen effizienten Algorithmus zur Lösung dieses Problems in linearer Zeitkomplexität bereit und implementieren ihn in C++. Dieses Problem kann auch mit anderen Techniken gelöst werden, aber der obige Algorithmus liefert

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der Teilzeichenfolgen, die aus einem einzelnen eindeutigen Zeichen bestehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!