Programme C++ : trouver la sous-séquence de nombres la plus longue avec la même rotation gauche et droite

Dans ce problème, nous devons trouver la longueur maximale de la sous-séquence avec la même rotation gauche et droite. La rotation à gauche signifie déplacer tous les caractères de la chaîne vers la gauche et déplacer le premier caractère à la fin. La rotation à droite signifie déplacer tous les caractères de chaîne vers la droite et déplacer le dernier caractère au début.

Énoncé du problème – On nous donne une chaîne str contenant des nombres et nous devons trouver une sous-séquence de longueur maximale avec la même rotation gauche et droite.

Exemple

Entrez -str="323232",

Sortie– 6

Explication – La sous-séquence la plus longue avec la même rotation gauche et droite est « 323232 ». Faites-le pivoter vers la gauche jusqu'à « 232323 » et faites-le pivoter vers la droite jusqu'à « 232323 ».

Entrez -str = '00010100'

Sortie– 6

Explication – La sous-séquence la plus longue avec la même rotation gauche et droite est "000000".

Entrez -str = '092312110431010'

Sortie– 6

Explication – Il existe 2 sous-séquences possibles de longueur 6 avec la même rotation gauche et droite. Le premier est « 010101 » et le second est « 101010 ».

Méthode 1

Dans cette méthode, nous trouverons toutes les sous-séquences possibles de la chaîne donnée. Après cela, nous vérifierons si la rotation gauche et droite de la chaîne est la même. Nous utiliserons une méthode récursive pour trouver toutes les sous-séquences possibles.

Algorithme

• Initialisez la variable globale "maxLen" à zéro pour stocker la longueur de la sous-séquence la plus longue avec la même rotation gauche et droite.

• Définissez la fonction isRightSameLeft() pour vérifier si les rotations gauche et droite de la chaîne sont les mêmes.

• Dans la fonction, utilisez la méthode substr() pour faire pivoter la chaîne vers la gauche et la droite.

La fonction

• getAllSubSeq() est utilisée pour trouver toutes les sous-séquences possibles d'une chaîne donnée.

• Définissez le cas de base. Si str est vide, nous obtenons la sous-séquence et exécutons la fonction isRightSameLeft() pour vérifier si la sous-séquence a la même rotation gauche et droite. Si tel est le cas, mettez à jour la valeur de la variable "maxLen" si sa longueur est supérieure à la valeur actuelle de "maxLen".

• Faites un appel récursif après avoir supprimé le premier caractère de "str" ​​​​et ajouté la chaîne "out".

• Après avoir supprimé le premier caractère et laissé la chaîne "out" inchangée, effectuez un autre appel de fonction récursif. Dans cet appel récursif, nous excluons le premier caractère de "str".

Exemple

#include <iostream>
#include <string>
using namespace std;

// Defining global variable to store the length of the longest subsequence according to the given condition
int maxLen = 0;
//  function to check if the string is the same after the left rotation
bool isRightSameLeft(string str) {
   int len = str.length();
   return str.substr(1, len - 1) + str[0] == str[len - 1] + str.substr(0, len - 1);
}
// function to get all subsequences of a string
void getAllSubSeqs(string str, string out) {
   // If the string is empty, we get the subsequences. Check if its left and right rotation is the same
   if (str.empty()) {
      if (isRightSameLeft(out))
          maxLen = max(maxLen, (int)out.length());
      return;
   }
   // Recursive case remove the first character from str, and add it to the output
   getAllSubSeqs(str.substr(1), out + str[0]);
   // remove the first character from str, and drop it
   if (str.length() > 1)
      getAllSubSeqs(str.substr(1), out);
}
int main() {
   string str = "323232";
   string out = "";
   getAllSubSeqs(str, out);
   cout << "The longest subsequence of str having same left and right rotation is " << maxLen;
   return 0;
}

Sortie

The longest subsequence of str having same left and right rotation is 6

Complexité temporelle - O(N*2N). Ici O(N) pour comparer les rotations gauche et droite et O(2N) pour trouver toutes les sous-séquences possibles.

Complexité spatiale - O(1) puisque nous n'utilisons pas d'espace supplémentaire.

Méthode 2

Ici, nous avons optimisé la méthode ci-dessus. Nous pouvons observer la solution de l’échantillon d’entrée. Les rotations gauche et droite d'une sous-séquence sont identiques uniquement si la sous-séquence contient le même caractère ou contient alternativement deux caractères différents et est de longueur paire.

Algorithme

• Utilisez deux boucles imbriquées pour combiner deux nombres quelconques.

• Définissez la variable 'cnt' pour trouver la longueur d'une sous-séquence contenant alternativement deux nombres, et initialisez-la à zéro.

• Définissez une "première" variable booléenne pour savoir si le caractère suivant doit être le i-ème ou le j-ème caractère.

• Utilisez une boucle pour parcourir la chaîne.

• Si first == true et str[k] - '0' == I, alternez la valeur de 'first' et incrémentez 'cnt' de 1.

• Si first == false et str[k] - '0' == j, alternez à nouveau la valeur de 'first' et incrémentez 'cnt' de 1.

• Si i et j ne sont pas égaux et que la valeur "cnt" est impaire, décrémentez-la de 1.

• Si la valeur cnt est supérieure à "res", mettez à jour la valeur de la variable "res".

Exemple

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

int getLongSubSeq(string str) {
   // Store the length of the string
   int len = str.size(), res = 0;
   // Traverse the all possible combination of two digits
   for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
          // to store the length of an alternating sequence of the current combination
          int cnt = 0;
          // to track the turn of the ith or jth digit
          bool first = true;
          // traverse the string
          for (int k = 0; k < len; k++) {
              // If the current digit is equal to I, and the first is true, increment the count
              if (first == true and str[k] - '0' == i) {
                  first = false;
                  cnt++;
              } else if (first == false and str[k] - '0' == j) {
                  // If the current digit is equal to j, and the first is false, increment the count
                  first = true;
                  cnt++;
              }
          }
          // If the sequence is odd and i and j are different, decrement the count
          if (i != j and cnt % 2 == 1)
              cnt--;
          // Update the answer
          res = max(cnt, res);
       }
   }
   return res;
}
int main() {
   string str = "00010100";
   cout << "The longest subsequence of str having same left and right rotation is " << getLongSubSeq(str);
   return 0;
}

Sortie

The longest subsequence of str having same left and right rotation is 6

Complexité temporelle - O(10*10*N) car nous trouvons des sous-séquences à partir de chaînes contenant des combinaisons de nombres.

Complexité spatiale - O(1) puisque nous n'utilisons pas d'espace dynamique.

Ce tutoriel nous apprend deux méthodes pour trouver la sous-séquence la plus longue contenant la même rotation gauche et droite. La première méthode est la méthode simple qui prend beaucoup de temps et nous ne pouvons pas l'utiliser pour des intrants importants.

La deuxième méthode est optimisée et sa complexité temporelle est presque égale à O(N).

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!