Maison >développement back-end >C++ >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.
Input 1: string str = "aabbbcccc"
Output: "4c3b2a"
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"
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.
À 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.
#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; }
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.
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!