Rechercher différentes sous-chaînes palindromiques dans une chaîne donnée à l'aide de la programmation dynamique

Présentation

Dans ce tutoriel, nous avons discuté d'une méthode pour trouver toutes les sous-chaînes palindromiques possibles à l'aide d'une chaîne d'entrée. Pour implémenter cette méthode de tâche, nous utilisons le langage de programmation C++ et ses fonctions.

Un palindrome est une chaîne qui se lit de la même manière d'avant en arrière et d'arrière en avant. Par exemple, Mom est une chaîne palindrome. Dans ce didacticiel, nous prendrons une chaîne et y trouverons toutes les sous-chaînes palindromes possibles.

La traduction chinoise de

Exemple 1

est :

Exemple 1

String = abcaa

Sortie

The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.

Dans l'exemple ci-dessus, la chaîne d'entrée peut générer 7 sous-chaînes palindromes : 'a', 'b', 'c', 'aa', 'aaa', 'aba' et 'aca'.

La traduction chinoise de

Exemple 2

est :

Exemple 2

String = “abcd”

Sortie

a, b, c, and d.

Dans l'exemple ci-dessus, seules 4 sous-chaînes palindromiques de longueur 1 peuvent être obtenues en utilisant la chaîne d'entrée. Puisqu’il n’y a pas de caractères répétés dans la chaîne d’entrée, aucune sous-chaîne n’a une longueur supérieure à 1.

Fonction utilisée pour exemple d'implémentation

• size() - Il s'agit d'une fonction de type chaîne qui renvoie le nombre de caractères dans la chaîne donnée. Il n'accepte pas de paramètres.

Grammaire

string_name.size();

Exemple

str.size();

• begin() - Cette fonction de bibliothèque est définie en STL. Il donne la valeur d'itération de départ du conteneur de carte.

Syntaxe : map_name.begin(); Exemple : mp.begin();

• end() - Cette fonction de bibliothèque est définie en STL. Il donne la valeur d'itération de fin du conteneur de carte.

Grammaire

map_name.end();

Exemple

mp.end();

• substr() - Il génère une sous-chaîne en utilisant la chaîne d'entrée. Il est défini dans le fichier d'en-tête string.h. Il accepte deux paramètres (pos, len). Pos est la valeur de départ de la sous-chaîne et len ​​est le nombre de caractères dans la sous-chaîne.

Grammaire

string_name.substr(pos, len);

Exemple

str.substr();

Algorithme

• Considérez une chaîne donnée et trouvez toutes les sous-chaînes palindromiques qu'elle contient.

• Trouvez toutes les sous-chaînes palindromiques de la chaîne d'entrée en itérant sur la chaîne.

• Créez deux tableaux pour les sous-chaînes palindromes de longueur impaire et paire.

• Stockez les valeurs de deux tableaux dans une carte de hachage.

• Imprimez toutes les valeurs stockées dans Hashmap.

• Le nombre de sous-chaînes est égal à la longueur de la carte de hachage. Parcourez la carte de hachage et imprimez chaque valeur. Utilisez une boucle for pour accéder à chaque élément de la carte et imprimer sa valeur associée. Enfin, le nombre de valeurs imprimées doit correspondre à la taille de la carte de hachage.

Exemple de logique 1

Dans cette section, nous implémentons l'un des exemples ci-dessus en utilisant les concepts du langage de programmation C++. Nous considérons une chaîne d’entrée dans la fonction main() et l’utilisons pour générer une sortie.

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

//user defined program to find the palindrome substrings
void palindromeSubStrings(string str){
   map<string, int> mp;
   int l = str.size();
   
   //store odd and even length palindrome substrings
   int R[2][l+1];
   
   //Using guards for effortless iteration over the input string and generating all palindrome
   // substrings
   str = "@" + str + "#";
   
   for (int i = 0; i <= 1; i++) {
      int r = 0;  
      R[i][0] = 0;

      int x = 1;
      while (x <= l){
            
         while (str[x - r - 1] == str[x + i + r])
            r++; 
           
         R[i][x] = r;
         int a = 1;
         while ((R[i][x - a] != r - a) && (a < r)){
            R[i][x + a] = min(R[i][x - a],r - a);
            a++;
         }
         r = max(r - a,0);
         x += a;
      }
   }
   //storing the substring without guards
   str = str.substr(1, l);
      
   mp[string(1, str[0])]=1;
   for (int x = 1; x <= l; x++){
      for (int y = 0; y <= 1; y++)
            for (int r = R[y][x]; r > 0; r--)
               mp[str.substr(x - r - 1, 2 * r + y)]=1;
         mp[string(1, str[x])]=1;
   }
      
   //print the palindrome substrings stored in the Hashmap
   cout << "Palindrome substrings are as listed: ";
   map<string, int>::iterator xx;
   for (xx = mp.begin(); xx!=mp.end(); ++xx)
      cout << (*xx).first << endl;
}
   
//Controlling code
int main(){
   //calling the user-defined function and passing a string as argument
   palindromeSubStrings("abcaa");
   return 0;
}

Sortie

Palindrome substrings are listed as:
a
aa
b
c

Exemple de logique 2

Nous implémentons un autre exemple en utilisant la méthode de programmation dynamique. Dans la programmation dynamique, les tâches sont divisées en sous-tâches et résolues individuellement pour réduire le temps et la complexité.

#include <iostream>
#include <vector>
using namespace std;
//User defined function to find the palindromic substring 
int find(string str){
   int a = str.size();
   //defined dpg array
      vector<vector<bool> > dpg(a, vector<bool>(a, false));
      for (int x = 0; x < a; x++) {

         dpg[x][x] = 1;
  
         if (x < a && str[x] == str[x + 1]) {
            dpg[x][x + 1] = 1;
         }
      }
   // Finding length of different substrings
   for (int l = 3; l <= a; l++) {
      for (int x = 0; x + l - 1 < a; x++){
         if (str[x] == str[x + (l - 1)]
         && dpg[x + 1][x + (l - 1) - 1]) {
            dpg[x][x + (l - 1)] = true;
         }
      }
   }
 
 
   vector<int> kmp(a, 0);
   for (int x = 0; x < a; x++) {
     
      int y = 0, m = 1;
      while (m + x < a) {
         if (str[y + x] == str[m + x]){
            dpg[m + x - y][m + x] = false;
            kmp[m++] = ++y;
         }
         else if (y > 0) {
            y = kmp[y - 1];
         }
         else {
            kmp[m++] = 0;
         }
      }
   }

   int cnt = 0;
   for (int x = 0; x < a; x++) {
      string str1;
      for (int y = x; y < a; y++) {
         str1 += str[y];
         if (dpg[x][y]) {
            //counting number of palindromic substrings formed using the string
               cnt++;
               cout << str1 << '\n';
         }
      }
   }
   cout << "Total number of palindromes are "
   << cnt << '\n';
   return 0;
}
 
//Controller
int main(){
   string str = "abaa";
   find(str);
   return 0;
}

Sortie

a
aba
b
aa
Total number of palindromes are 4

Conclusion

Dans ce tutoriel, nous avons développé deux méthodes pour trouver toutes les sous-chaînes palindromes possibles dans une chaîne donnée. Nous comprenons la tâche à travers deux exemples et écrivons un exemple de code en utilisant le langage de programmation C++. Nous utilisons des cartes de hachage et des vecteurs pour stocker les sous-chaînes palindromiques afin d'implémenter l'exemple. L'utilisation de la carte de hachage aide à faire correspondre les paires clé-valeur et nous pouvons utiliser de nombreuses fonctions de hachage selon nos besoins. Nous avons également utilisé certaines fonctions de la bibliothèque pour implémenter les exemples.

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!