Trouver la sous-chaîne de parité impaire la plus longue

Présentation

Dans ce tutoriel, nous développons une méthode pour trouver la sous-chaîne de parité impaire de longueur maximale. La parité impaire dans une sous-chaîne signifie que 1 est répété un nombre impair de fois dans la chaîne. La parité en C++ définit le numéro du jeu de bits et est 1 en nombre. Il existe deux types de parité : la parité paire et la parité impaire.

Lorsque le nombre total de « 1 » dans la représentation binaire est impair, on parle de chaîne de parité impaire. Dans ce didacticiel, nous utilisons les concepts de programmation C++ pour trouver la sous-chaîne de parité impaire de longueur maximale.

Mise en œuvre 1

String = 101100

Output = 6

Dans l'exemple ci-dessus, la longueur de la sous-chaîne de parité impaire maximale est de 6 et la sous-chaîne peut être 011100. Le nombre total de 1 dans cette sous-chaîne est 3, ce qui est un nombre impair. Faites-en une sous-chaîne de parité impaire.

Mise en œuvre 2

String = 1011010

Output = 6

Dans l'exemple ci-dessus, la longueur maximale de la sous-chaîne de parité impaire dans la chaîne donnée est de 6. Une sous-chaîne possible pourrait être 011010 puisqu'elle contient un total de 3 "1", ce qui en fait une sous-chaîne à parité impaire.

Algorithme

• Créez une variable de compteur ct pour compter les 1 dans la chaîne d'entrée.

• Si ct = 0, la sous-chaîne de parité impaire ne peut pas être formée car la chaîne d'entrée ne contient que 0.

• Si le nombre total de 1 dans la chaîne d'entrée est impair, la longueur de la sous-chaîne est égale à la longueur de la chaîne.

• Lorsque la valeur de la variable ct est un nombre pair, la sous-chaîne peut être composée de deux possibilités.

• Trouvez la sous-chaîne de parité impaire la plus longue.

• Longueur d’impression.

Exemple

Nous implémentons l'exemple 2 en C++ et utilisons la fonction length() de la classe string pour trouver la longueur de la chaîne d'entrée et la sous-chaîne résultante.

#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));
}

Sortie

The maximum length of the odd parity substring is: 6

Conclusion

Dans ce tutoriel, nous avons développé une méthode pour trouver la longueur de la plus longue sous-chaîne impaire-pair à partir d'une chaîne d'entrée donnée. La longueur de la sous-chaîne de parité impaire est calculée à l'aide d'une variable de compteur et en définissant différentes conditions if pour celle-ci.

Nous avons utilisé la fonction length() de la classe string pour aider à trouver la longueur de la sous-chaîne et la valeur d'index de la chaîne d'entrée. La valeur d'index génère la sous-chaîne.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!