Hitung tiga subrentetan tidak bertindih dan gabungkannya untuk membentuk palindrom

Pengenalan

Dalam tutorial ini, kami akan menghuraikan kaedah untuk mencari tiga subrentetan tidak bertindih daripada rentetan s tertentu, dan apabila semua subrentetan digabungkan bersama, ia membentuk palindrom. Untuk menyelesaikan tugasan ini, kami menggunakan fungsi kelas rentetan bahasa pengaturcaraan C++.

Palindrom dalam rentetan bermakna rentetan membaca sama dalam kedua-dua arah ke hadapan dan ke belakang. Contoh rentetan palindrom ialah Puan.

Andaikan terdapat rentetan "s", dan subrentetan ialah a, b, c. Apabila anda menggabungkan a, b, dan c, ia membentuk rentetan palindrom. Ini adalah contoh memahami logik masalah.

Penerangan ayat

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

Apabila kita menggabungkan ketiga-tiga substring, rentetan yang terhasil ialah rentetan palindrom, iaitu abbbacbba.

Tatabahasa

Fungsi

size() tergolong dalam kelas rentetan dan digunakan untuk mendapatkan saiz rentetan input dan panjang aksaranya.

string_name,size();  

Algoritma

• Dapatkan rentetan input.

• Mulakan pembolehubah pembilang yang digunakan untuk menjejak bilangan subrentetan palindromik.

• Gunakan 3 bersarang untuk gelung untuk menjana 3 kemungkinan subrentetan panjang yang ditentukan.

• Gelung dalam pertama dimulakan daripada 0 kepada panjang rentetan - 3.

• Gelung dalam kedua dimulakan kepada panjang rentetan - 2 daripada gelung dalam pertama + 1.

• Gelung luar dimulakan daripada gelung kedua + 1 kepada panjang rentetan - 1.

• Selepas mencari semua subrentetan, gabungkan mereka.

• Semak sama ada palindrom subrentetan wujud dan jika ya, naikkan nilai pemboleh ubah pembilang.

• Cetak nilai pemboleh ubah pembilang.

Contoh

Untuk melaksanakan algoritma di atas menggunakan C++, kami mengambil rentetan input dan menjana semua kemungkinan gabungan subrentetan dan mempertimbangkan subrentetan palindromik sahaja. Jika subrentetan sedemikian mungkin, pembolehubah pembilang akan dinaikkan. Cetak keputusan pembolehubah pembilang.

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

Output

The possible number of substrings are: 4

Kesimpulan

Kami membangunkan kaedah untuk mencari subrentetan sah yang membentuk palindrom. Untuk melaksanakan penyelesaian ini kami menggunakan gelung C++ dan jika keadaan. Untuk melaksanakan salah satu contoh menggunakan C++, kami menggunakan fungsi size() dan gelung bersarang. Gelung bersarang membantu mencari subrentetan dengan panjang yang berbeza dan fungsi size() mengembalikan saiz rentetan.

Atas ialah kandungan terperinci Hitung tiga subrentetan tidak bertindih dan gabungkannya untuk membentuk palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!