Calculez trois sous-chaînes qui ne se chevauchent pas et concaténez-les pour former un palindrome

Présentation

Dans ce tutoriel, nous développerons une méthode pour trouver trois sous-chaînes qui ne se chevauchent pas à partir d'une chaîne s donnée, et lorsque toutes les sous-chaînes sont combinées ensemble, elles forment un palindrome. Pour résoudre cette tâche, nous utilisons la fonctionnalité de classe de chaînes du langage de programmation C++.

Un palindrome dans une chaîne signifie que la chaîne se lit de la même manière dans les deux sens. Un exemple de chaîne palindrome est Madame.

Supposons qu'il y ait une chaîne "s" et que les sous-chaînes soient a, b, c. Lorsque vous combinez a, b et c, ils forment une chaîne palindrome. Ceci est un exemple de compréhension de la logique du problème.

Explication des phrases

String s = “abbacab”      
Acceptable substrings of length 3 are: “abb”, “bac”, and “bba”.

Lorsque nous concaténons les trois sous-chaînes, la chaîne résultante est une chaîne palindrome, qui est abbbacbba.

Grammaire

La fonction

size() appartient à la classe string et est utilisée pour obtenir la taille de la chaîne d'entrée et sa longueur de caractères.

string_name,size();  

Algorithme

• Obtenir la chaîne d'entrée.

• Initialisez une variable de compteur utilisée pour suivre le nombre de sous-chaînes palindromiques.

• Utilisez 3 boucles for imbriquées pour générer 3 sous-chaînes possibles de longueur définie.

• La première boucle interne est initialisée de 0 à la longueur de la chaîne - 3.

• La deuxième boucle intérieure est initialisée à la longueur de la chaîne - 2 à partir de la première boucle intérieure + 1.

• La boucle extérieure est initialisée à partir de la deuxième boucle + 1 jusqu'à la longueur de la chaîne - 1.

• Après avoir trouvé toutes les sous-chaînes, concaténez-les.

• Vérifiez si le palindrome de la sous-chaîne existe et si c'est le cas, incrémentez la valeur de la variable du compteur.

• Imprimer la valeur de la variable du compteur.

Exemple

Pour implémenter l'algorithme ci-dessus en utilisant C++, nous prenons la chaîne d'entrée et générons toutes les combinaisons possibles de sous-chaînes et ne considérons que ces sous-chaînes palindromiques. Si une telle sous-chaîne est possible, la variable compteur sera incrémentée. Imprime le résultat de la variable compteur.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function to check formed substrings are palindrome or not
bool isStringPalin(int a, int b, int c, int d, int x, int y, string st){
   int begin = a, stop = y;
   while (begin < stop) {
      if (st[begin] != st[stop])
         return false;
 
      begin++;
      if (begin == b + 1)
         begin = c;
      stop--;
      if (stop == x - 1)
         stop = d;
   }
   return true;
}
 
// User defined function to count the number of useful substrings
int countSubString(string st){
   //Counting variable to count and return the number of substrings
   int ct = 0;
   int l = st.size();
 
   //It is to select the first substring
   for (int a = 0; a < l - 2; a++) {
      for (int b = a; b < l - 2; b++){
 
         // This loop selects the second useful substring
         for (int c = b + 1; c < l - 1; c++) {
            for (int d = c; d < l - 1; d++) {
 
               // this for loop will select the third substring
               for (int x = d + 1; x < l; x++) {
                  for (int y = x; y < l; y++) {
 
                     // If condition to check the selected substrings are forming palindrome or not
                     if (isStringPalin(a, b, c, d, x, y, st)) {
                        ct++;
                     }
                  }
               }
            }
         }
      }
   }
   // returning the count variable that stores the number of useful substrings
   return ct;
}
 
// Controlling code
int main(){
   string st = "abcab";
   cout << "The possible number of substrings are: "<< countSubString(st);
 
   return 0;
}

Sortie

The possible number of substrings are: 4

Conclusion

Nous avons développé une méthode pour trouver des sous-chaînes valides qui forment des palindromes. Pour implémenter cette solution, nous avons utilisé des boucles C++ et des conditions if. Pour implémenter l'un des exemples en C++, nous avons utilisé la fonction size() et des boucles imbriquées. Les boucles imbriquées aident à trouver des sous-chaînes de différentes longueurs et la fonction size() renvoie la taille de la 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!