Finden Sie den längsten Teilstring mit ungerader Parität

Einführung

In diesem Tutorial entwickeln wir eine Methode, um die Teilzeichenfolge mit ungerader Parität maximaler Länge zu ermitteln. Ungerade Parität in einer Teilzeichenfolge bedeutet, dass 1 in der Zeichenfolge ungerade oft wiederholt wird. Parität in C++ definiert die Bitsatznummer und ist in Zahlen 1. Es gibt zwei Arten von Parität: gerade Parität und ungerade Parität.

Wenn die Gesamtzahl der „1“ in der Binärdarstellung ungerade ist, spricht man von einer ungeraden Paritätszeichenfolge. In diesem Tutorial verwenden wir C++-Programmierkonzepte, um die Teilzeichenfolge mit ungerader Parität maximaler Länge zu ermitteln.

Implementierung 1

String = 101100

Output = 6

Im obigen Beispiel beträgt die Länge der maximalen Teilzeichenfolge mit ungerader Parität 6, und die Teilzeichenfolge kann 011100 sein. Die Gesamtzahl der Einsen in dieser Teilzeichenfolge beträgt 3, was einer ungeraden Zahl entspricht. Machen Sie daraus einen Teilstring mit ungerader Parität.

Implementierung 2

String = 1011010

Output = 6

Im obigen Beispiel beträgt die maximale Länge der Teilzeichenfolge mit ungerader Parität in der angegebenen Zeichenfolge 6. Ein möglicher Teilstring könnte 011010 sein, da er insgesamt 3 „1“ enthält, was ihn zu einem Teilstring mit ungerader Parität macht.

Algorithmus

• Erstellen Sie eine Zählervariable ct, um die Einsen in der Eingabezeichenfolge zu zählen.

• Wenn ct = 0, kann die Teilzeichenfolge mit ungerader Parität nicht gebildet werden, da die Eingabezeichenfolge nur 0 enthält.

• Wenn die Gesamtzahl der Einsen in der Eingabezeichenfolge ungerade ist, ist die Länge der Teilzeichenfolge gleich der Länge der Zeichenfolge.

• Wenn der Wert der ct-Variablen eine gerade Zahl ist, kann die Teilzeichenfolge aus zwei Möglichkeiten bestehen.

• Finden Sie die längste Teilzeichenfolge mit ungerader Parität.

• Drucklänge.

Beispiel

Wir implementieren Beispiel 2 in C++ und verwenden die Funktion length() der String-Klasse, um die Länge des Eingabestrings und des resultierenden Teilstrings zu ermitteln.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function for calculating the index value of string
int indexOfString(string st, char ch, int j){
   for(; j < st.length(); j++)
      if(st[j] == ch)
      return j;      
      return -1;
}
//finding the lsat index value of the string
int lastIndexOfString(string st,char ch,int j){
   for(; j >= 0; j--)
      if(st[j] == ch)
   return j;
   return -1;
}
 
//user defined function to find the length of the longest odd parity substring
int maxSubstring(string s, int l){

   //variable for counting 1s
   int ct = 0;
   for (int j = 0; j < l; j++)
      if (s[j] == '1')
         ct++;

   //different counter variable conditions
   if (ct == 0)
      return 0;
       
   if (ct % 2 == 1)
      return l;
       
   int firstTime = indexOfString(s,'1',0);
   int secondTime = indexOfString(s,'1', firstTime + 1);

   int lastTime = lastIndexOfString(s,'1',s.length()-1);
   int secondLastTime = lastIndexOfString(s,'1', lastTime - 1);

   return max(lastTime, l - firstTime - 1);
}

// Controller
int main(){
   string s = "1011010";
   int l = s.length();
   cout<<"The maximum length of the odd parity substring is:" <<(maxSubstring(s, l));
}

Ausgabe

The maximum length of the odd parity substring is: 6

Fazit

In diesem Tutorial haben wir eine Methode entwickelt, um die Länge des längsten ungeraden/geraden Teilstrings aus einem bestimmten Eingabestring zu ermitteln. Die Länge der Teilzeichenfolge mit ungerader Parität wird mithilfe einer Zählervariablen und der Definition verschiedener IF-Bedingungen dafür berechnet.

Wir haben die Funktion length() der String-Klasse verwendet, um die Länge des Teilstrings und den Indexwert des Eingabestrings zu ermitteln. Der Indexwert generiert den Teilstring.

Das obige ist der detaillierte Inhalt vonFinden Sie den längsten Teilstring mit ungerader Parität. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!