Requête de sous-chaîne palindromique en C++

Dans ce tutoriel, nous devons résoudre la requête de sous-chaîne palindromique d'une chaîne donnée. La résolution des requêtes de sous-chaînes palindromes est beaucoup plus complexe que la résolution de requêtes classiques en C++. Cela nécessite un code et une logique plus complexes.

Dans ce tutoriel, nous avons fourni des requêtes string str et Q substring [L...R], chacune ayant deux valeurs L et R. Notre objectif est d'écrire un programme qui résout une requête pour déterminer si la sous-chaîne[L...R] est un palindrome. Nous devons déterminer si la sous-chaîne formée dans la plage L à R est un palindrome pour résoudre chaque requête. Par exemple : 

Let's input "abbbabaaaba" as our input string.
The queries were [3, 13], [3, 11], [5, 8], [8, 12]
It is necessary to determine whether the substring is a plaindrome
A palindrome is "abaaabaaaba" (3, 13) .
It is not possible to write "baaa" as a palindrome [3, 11].
As in [5, 8]: "aaab" cannot be a palindrome.
There is a palindrome in "baaab" ([3, 12]).

Méthode de solution

Méthode naïve

Ici, nous devons trouver le palindrome en vérifiant si la sous-chaîne est comprise entre la plage d'index L à R. Par conséquent, nous devons effectuer une requête pour toutes les sous-chaînes. Vérifier pour voir si c'est un palindrome. Puisqu'il existe des requêtes Q, chaque requête prend 0(N) de temps pour répondre. Cela prend 0 (Q.N) de temps dans le pire des cas.

Exemple

#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
   int i, length;
   int flag = 0;
   length = str.length();
   for(i=0;i < length ;i++){
      if(str[i] != str[length-i-1]) {
         flag = 1; break;
      }
   }
   if (flag==1)
      return 1;
   return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
   for(int i = 0; i < Q; i++){
      isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"Palindrome\n":cout<<"Not palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

Sortie

Palindrome
Palindrome
Not palindrome!

Méthode de programmation dynamique

L'utilisation de la méthode de programmation dynamique pour résoudre le problème est une option efficace. Pour résoudre ce problème, nous devons créer un tableau DP, qui est un tableau bidimensionnel contenant une valeur booléenne indiquant si la sous-chaîne[i...j] est un palindrome de DP[i][j].

créera cette matrice DP et vérifiera toutes les valeurs L-R pour chaque requête.

Exemple

#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
   int length = str.size();
   int i, j;
   for (i = 0; i < length; i++) {
      for (j = 0; j < length; j++)
         DP[i][j] = 0;
   }
   for (j = 1; j <= length; j++) {
      for (i = 0; i <= length - j; i++) {
         if (j <= 2) {
            if (str[i] == str[i + j - 1])
               DP[i][i + j - 1] = 1;
         }
         else if (str[i] == str[i + j - 1])
            DP[i][i + j - 1] = DP[i + 1][i + j - 2];
      }
   }
}
void solveAllQueries(string str, int Q, int query[][2]){
   int DP[50][50];
   computeDP(DP, str);
   for(int i = 0; i < Q; i++){
      DP[query[i][0] - 1][query[i][1] - 1]?cout
      <<"not palindrome!\n":cout<<"palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

Sortie

palindrome!
not palindrome!
palindrome!

Conclusion

Dans ce tutoriel, nous avons appris à résoudre une requête de sous-chaîne palindromique à l'aide du code C++. Nous pouvons également écrire ce code en Java, Python et d'autres langages. Ce code est l’un des plus complexes et des plus longs. Les requêtes palindrome sont plus difficiles que les requêtes de sous-chaînes classiques et nécessitent une logique très précise. Nous espérons que vous avez trouvé ce tutoriel utile.

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!