Cari subrentetan palindromik yang berbeza dalam rentetan tertentu menggunakan pengaturcaraan dinamik

Pengenalan

Dalam tutorial ini, kami membincangkan kaedah untuk mencari semua subrentetan palindromik yang mungkin menggunakan rentetan input. Untuk melaksanakan kaedah tugasan ini kami menggunakan bahasa pengaturcaraan C++ dan fungsinya.

Palindrom ialah rentetan yang berbunyi sama dari hadapan ke belakang dan dari belakang ke hadapan. Contohnya, Ibu ialah rentetan palindrom. Dalam tutorial ini, kami akan mengambil rentetan dan mencari semua substring palindrom yang mungkin di dalamnya.

Terjemahan bahasa Cina bagi

Contoh 1

ialah:

Contoh 1

String = abcaa

Output

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

Dalam contoh di atas, rentetan input boleh menjana 7 subrentetan palindromik: 'a', 'b', 'c', 'aa', 'aaa', 'aba' dan 'aca'.

Terjemahan bahasa Cina bagi

Contoh 2

ialah:

Contoh 2

String = “abcd”

Output

a, b, c, and d.

Dalam contoh di atas, hanya 4 subrentetan palindromik dengan panjang 1 boleh diperoleh menggunakan rentetan input. Oleh kerana tiada aksara berulang dalam rentetan input, tiada subrentetan mempunyai panjang lebih daripada 1.

Fungsi yang digunakan sebagai contoh pelaksanaan

• size() − Ini ialah fungsi seperti rentetan yang mengembalikan bilangan aksara dalam rentetan yang diberikan. Ia tidak menerima parameter.

Tatabahasa

string_name.size();

Contoh

str.size();

• begin() − Fungsi perpustakaan ini ditakrifkan dalam STL. Ia memberikan nilai lelaran permulaan bekas peta.

Sintaks: map_name.begin(); Contoh: mp.begin();

• end() − Fungsi perpustakaan ini ditakrifkan dalam STL. Ia memberikan nilai lelaran akhir bekas peta.

Tatabahasa

map_name.end();

Contoh

mp.end();

• substr() − Ia menjana subrentetan menggunakan rentetan input. Ia ditakrifkan dalam fail pengepala string.h. Ia menerima dua parameter (pos, len). Pos ialah nilai permulaan subrentetan dan len ialah bilangan aksara dalam subrentetan.

Tatabahasa

string_name.substr(pos, len);

Contoh

str.substr();

Algoritma

• Pertimbangkan rentetan yang diberikan dan cari semua subrentetan palindrom di dalamnya.

• Cari semua subrentetan palindromik rentetan input dengan mengulangi rentetan itu.

• Buat dua tatasusunan untuk subrentetan palindrom ganjil dan genap.

• Simpan nilai dua tatasusunan dalam peta cincang.

• Cetak semua nilai yang disimpan dalam Hashmap.

• Bilangan subrentetan adalah sama dengan panjang peta cincang. Lelaran melalui peta cincang dan cetak setiap nilai. Gunakan gelung for untuk mengakses setiap item dalam peta dan mencetak nilai yang berkaitan dengannya. Akhir sekali, bilangan nilai yang dicetak hendaklah sepadan dengan saiz peta cincang.

Logik 1 Contoh

Dalam bahagian ini, kami melaksanakan salah satu daripada contoh di atas menggunakan konsep bahasa pengaturcaraan C++. Kami menganggap rentetan input dalam fungsi main() dan menggunakannya untuk menjana output.

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

Output

Palindrome substrings are listed as:
a
aa
b
c

Contoh Logik 2

Kami sedang melaksanakan satu lagi contoh menggunakan kaedah pengaturcaraan dinamik. Dalam pengaturcaraan dinamik, tugasan dipecahkan kepada subtugas dan diselesaikan secara individu untuk mengurangkan masa dan kerumitan.

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

Output

a
aba
b
aa
Total number of palindromes are 4

Kesimpulan

Dalam tutorial ini, kami membangunkan dua kaedah untuk mencari semua subrentetan palindrom yang mungkin dalam rentetan tertentu. Kami memahami tugas melalui dua contoh dan menulis kod sampel menggunakan bahasa pengaturcaraan C++. Kami menggunakan peta hash dan vektor untuk menyimpan subrentetan palindromik untuk melaksanakan contoh. Penggunaan peta cincang membantu dalam memadankan pasangan nilai utama dan kami boleh menggunakan banyak fungsi cincang mengikut keperluan kami. Kami juga menggunakan beberapa fungsi perpustakaan untuk melaksanakan contoh.

Atas ialah kandungan terperinci Cari subrentetan palindromik yang berbeza dalam rentetan tertentu menggunakan pengaturcaraan dinamik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!