Pertanyaan subrentetan palindromik dalam C++

Dalam tutorial ini, kita perlu menyelesaikan pertanyaan subrentetan palindromik bagi rentetan yang diberikan. Menyelesaikan pertanyaan subrentetan palindrom adalah lebih kompleks daripada menyelesaikan pertanyaan biasa dalam C++. Ia memerlukan kod dan logik yang lebih kompleks.

Dalam tutorial ini, kami telah menyediakan pertanyaan substring str dan Q [L...R], setiap satunya mempunyai dua nilai L dan R. Matlamat kami adalah untuk menulis atur cara yang menyelesaikan pertanyaan untuk menentukan sama ada subrentetan[L...R] ialah palindrom. Kita mesti menentukan sama ada subrentetan yang terbentuk dalam julat L hingga R adalah palindrom untuk menyelesaikan setiap pertanyaan. Contohnya-

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]).

Kaedah penyelesaian

Kaedah naif

Di sini, kita mesti menyemak sama ada subrentetan antara julat indeks L hingga R. Oleh itu, kita perlu menyemak semua pertanyaan subrentetan satu demi satu untuk menentukan sama ada ia adalah palindrom. Oleh kerana terdapat pertanyaan Q, setiap pertanyaan mengambil masa 0(N) untuk menjawab. Ia mengambil masa 0(Q.N) dalam kes yang paling teruk.

Contoh

#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;
}

Output

Palindrome
Palindrome
Not palindrome!

Kaedah pengaturcaraan dinamik

#🎜🎜🎜#🎜 adalah pilihan yang berkesan untuk menyelesaikan masalah . Untuk menyelesaikan masalah ini, kita perlu mencipta tatasusunan DP, iaitu tatasusunan dua dimensi yang mengandungi nilai boolean yang menunjukkan sama ada subrentetan[i...j] ialah palindrom DP[i][j].

akan mencipta matriks DP ini dan menyemak semua nilai L-R untuk setiap pertanyaan.

Contoh

#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;
}

Output

palindrome!
not palindrome!
palindrome!

Kesimpulan

Dalam tutorial C ini kami mempelajari substring menggunakan kod Palindro++ pertanyaan. Kita juga boleh menulis kod ini dalam java, python dan bahasa lain. Kod ini adalah salah satu yang paling kompleks dan bertele-tele. Pertanyaan Palindrome adalah lebih sukar daripada pertanyaan subrentetan biasa dan memerlukan logik yang sangat tepat. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Pertanyaan subrentetan palindromik dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!