Maison >développement back-end >C++ >chaîne chiffrée

chaîne chiffrée

王林
王林avant
2023-09-08 10:37:021143parcourir

chaîne chiffrée

Le cryptage est une technique qui modifie les données en utilisant certaines techniques ou certaines étapes pour les transformer en un autre type d'informations ou à partir desquelles les informations précédentes ne peuvent pas être directement collectées. Pour le cryptage, nous devons suivre certaines étapes fixées pour le type de cryptage spécifique.

Dans cette question, nous obtiendrons une chaîne et nous devrons la chiffrer en suivant les étapes indiquées -

  • Nous devons d’abord obtenir toutes les sous-chaînes contenant les mêmes caractères et remplacer cette sous-chaîne par un seul caractère suivi de la longueur de la sous-chaîne.

  • Maintenant, changez la longueur en valeur hexadécimale et tous les caractères de la valeur hexadécimale doivent être modifiés en minuscules.

  • Enfin, inversez toute la chaîne.

Exemple

Input 1: string str = "aabbbcccc"
Output: "4c3b2a"

Instructions

Tout d'abord, nous obtiendrons toutes les sous-chaînes contenant le même nombre de caractères et les remplacerons par la fréquence des caractères, ce qui nous donnera la chaîne "a2b3c4". Nous modifions maintenant la longueur en valeur hexadécimale, mais 2, 3 et 4 ont la même valeur sous forme hexadécimale. Enfin, nous inversons la chaîne et le résultat final sera 4c3b2a.

Input2: string str = "oooooooooooo"
Output: "co"

Instructions

Tout d'abord, nous convertissons la chaîne en chaîne de fréquence "o12". Maintenant, la valeur hexadécimale de 12 est C, nous la changeons en minuscule, c'est-à-dire c et la remplaçons dans la chaîne, puis inversons la chaîne.

Méthode

À partir de l’exemple ci-dessus, nous avons une idée du problème, passons maintenant à la partie implémentation -

  • Dans l'implémentation, nous allons d'abord implémenter une fonction qui prend l'entrée sous forme d'entier et renvoie une chaîne comme valeur de retour.

  • Cette fonction sera utilisée pour convertir l'entier donné en valeur hexadécimale avec une modification, c'est-à-dire en utilisant des lettres anglaises minuscules au lieu de caractères anglais majuscules.

  • Nous définirons une autre fonction dans laquelle nous parcourrons la chaîne en utilisant une boucle for puis pour la sous-chaîne du même caractère, nous utiliserons une boucle while jusqu'à ce que nous trouvions un caractère égal au caractère actuel.

  • Nous allons calculer la fréquence, la changer en valeur hexadécimale et l'ajouter à la chaîne avec le caractère d'index actuel.

  • Enfin, nous inversons la chaîne et la renvoyons à la fonction principale pour l'impression.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to convert the integer to hexadecimal values 
string convertToHexa(int val){
   string res = ""; // string to store the result     
   while(val != 0){
      int cur = val %16; // getting the mode of the current value         
      if(cur < 10){
         res += '0' + cur;
       }
      else{
         res += 87 + cur; // adding 87 to get the lowercase letters 
      }
      val /= 16; // updating the current value 
   }
   return res;
}

// function to encrypt the string 
string encrypt(string str){
   int len = str.length(); // getting the length of the string 
   int freq = 0; // variable to store the frequency 
   string ans = ""; // string to store the answer    
   
   // traversing over the string 
   for(int i=0; i<len; i++){
      int j = i; // variable to keep track the substring with the same character
      while(j < len && str[j] == str[i]){
         j++;
      }
      freq = j-i;
      ans += str[i];
      
      // calling the function to get the hexadecimal value 
      string hexaValue = convertToHexa(freq);
      ans += hexaValue;        
      i = j-1;
   } 
   
   // reversing the string 
   reverse(ans.begin(), ans.end());
   return ans;
}

// main function 
int main(){
   string str = "aaabbbbccccccccccc"; // given string  
   
   // calling the function to get the encrypted string
   cout<<"The given string after the encryption is: "<<encrypt(str)<<endl;
   return 0;
}

Sortie

The given string after the encryption is: bc4b3a

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la taille de la chaîne donnée. Il nous a fallu N temps pour parcourir la chaîne, tandis que l'inversion de la chaîne a pris moins de N temps.

La complexité spatiale du code ci-dessus pour stocker la chaîne finale est O(N), si nous l'ignorons, aucun espace supplémentaire ne sera utilisé.

Attention

Le cryptage peut être effectué d'une infinité de façons, et il suffit de définir les règles pour crypter les clés. La principale caractéristique du chiffrement est qu’il doit donner à chaque fois le même résultat pour la même entrée.

Conclusion

Dans ce tutoriel, nous avons implémenté un code qui crypte une chaîne donnée en fonction de règles. Nous devons d'abord obtenir des sous-chaînes contenant des éléments du même type et les remplacer par des caractères et leurs fréquences. Ensuite, nous changeons la fréquence en un nombre hexadécimal et enfin inversons la chaîne entière. La complexité temporelle du code ci-dessus est 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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer