Bilangan minimum aksara yang perlu diganti supaya rentetan itu disatukan menjadi rentetan palindrom dengan panjang K

Menjejaki bilangan minimum aksara untuk menukar rentetan yang diberikan kepada pautan subrentetan palindromik panjang K ialah masalah biasa dalam bidang kawalan rentetan. Rentetan yang dibaca dalam langkah yang sama dan terbalik dipanggil rentetan palindrom. Contohnya, "radar" atau "tahap". Artikel ini akan merangkumi konsep asas, kaedah dan strategi pengoptimuman yang berpotensi untuk menyelesaikan masalah ini dengan berkesan. Menjelang akhir artikel ini, pembaca akan dapat menangani masalah manipulasi rentetan yang serupa kerana mereka akan mempunyai pemahaman lengkap tentang langkah-langkah yang diperlukan

Masalah akan diterangkan secara terperinci dalam perenggan berikut, dan kemudian kelebihan dan kekurangan setiap kaedah akan dibincangkan. Kaedah terpilih diperiksa dengan teliti dan contoh kod disediakan untuk menunjukkan cara menggunakannya. Kami juga akan mengkaji kerumitan masa setiap kaedah untuk melihat keberkesanan kaedah tersebut di bawah bilangan input yang berbeza

Kaedah penggunaan

• Kaedah Brute-Force

• Pendekatan Tingkap Gelongsor

Pendekatan Brute-Force

Pendekatan Brute-Force

The Brute-Force Pendekatan untuk mencari aksara paling sedikit untuk digantikan untuk membentuk rangkaian rentetan rentetan palindromik K-panjang termasuk memeriksa semua subrentetan panjang K yang mungkin dalam rentetan yang diberikan. dikosongkan dan ke kanan, pada permulaan dan akhir subrentetan aksara K, mulakan pembolehubah untuk menjejaki penggantian paling sedikit, dan lelaran atas rentetan, menaik taraf tetingkap dengan penunjuk yang betul bergerak satu langkah ke kanan setiap kali. semak sekiranya ia boleh menjadi palindrom dengan membandingkan aksara dari kiri dan kanan, dan hitung bilangan penggantian yang diperlukan sekiranya ia bukan palindrom Jejaki penggantian paling sedikit yang ditemui setakat ini daripada rentetan. Hasilnya ialah penggantian paling sedikit yang diperlukan untuk merealisasikan subrentetan palindromik K-panjang yang ditentukan Dalam apa jua keadaan, pendekatan ini mempunyai kerumitan masa yang tinggi, menjadikannya membazir untuk rentetan besar.

Algoritma

• Pertimbangkan setiap subrentetan panjang K semasa anda mengulangi rentetan yang disediakan.

• Sahkan sama ada setiap subrentetan ialah palindrom

• Kira bilangan aksara yang perlu ditukar jika ia bukan palindrom.

• Simpan sesedikit mungkin subrentetan yang perlu diganti

• Buat palindrom dengan menukar aksara dalam subrentetan penggantian minimum.

Contoh

#include <iostream>
#include <string>
using namespace std;

string minimalReplacementPalindromeSubstring(const string& str, int K) {
   int n = str.length();
   string minReplacementSubstr;

   for (int i = 0; i <= n - K; i++) {
      string substr = str.substr(i, K);
      int replacements = 0;
      for (int j = 0; j < K / 2; j++) {
         if (substr[j] != substr[K - 1 - j]) {
            replacements++;
         }
      }

      if (replacements < minReplacementSubstr.length() || minReplacementSubstr.empty()) {
         minReplacementSubstr = substr;
      }
   }

   return minReplacementSubstr;
}

int main() {
   string input = "iurefhuhfrati";
   int K = 4;

   string result = minimalReplacementPalindromeSubstring(input, K);
   cout << "Minimal Replacement Substring: " << result << endl;

   return 0;
}

Output

Minimal Replacement Substring: rati

Kaedah tingkap gelongsor

Pendekatan tingkap gelongsor boleh digunakan untuk menyelesaikan masalah dengan cekap, termasuk operasi subarray atau substring. Dalam kes penyambungan rentetan mencari bilangan minimum aksara untuk mencipta rentetan palindrom dengan panjang K, kaedah ini terdiri daripada mengekalkan tetingkap bersaiz tetap (subrentetan) aksara K semasa menavigasi rentetan input

Pengiraan menetapkan dua penunjuk 'kiri' dan 'kanan', pada mulanya menunjukkan permulaan dan akhir subrentetan aksara K. Ia kemudian menentukan bilangan penggantian yang diperlukan untuk menukar subrentetan ini kepada palindrom. Untuk menjejaki bilangan minimum penggantian yang diperlukan, pembolehubah 'min_replacements' dimulakan.

Algoritma

• Tetapkan dua penunjuk, kiri dan kanan, masing-masing menunjuk ke permulaan dan penghujung subrentetan aksara utama K.

• Menentukan bilangan penggantian yang dijangka menukar subrentetan kepada palindrom.

• Untuk menjejaki bilangan minimum penggantian yang diperlukan, mulakan min_replacements berubah

• Kemas kini tetingkap dengan menggerakkan penunjuk kanan satu kedudukan ke kanan

• Jika tetingkap semasa ialah palindrom, gerakkan penunjuk kanan

• Kira jumlah penggantian yang diperlukan dan, jika perlu, tukar min_replacements jika tetingkap semasa bukan palindrom.

• Untuk mengemas kini tetingkap, gerakkan penunjuk kiri satu ruang ke kanan.

• Sehingga kesimpulan rentetan, langkah ulang 4 hingga 7.

• Watak-watak subrentetan hendaklah digantikan dengan sesedikit mungkin penggantian

Contoh

#include <iostream>
#include <string>
using namespace std;

int minReplacementsForPalindrome(string s, int k) {
   int left = 0, right = k - 1, min_replacements = 0;
   while (right < s.length()) {
      int i = left, j = right;
      while (i < j) {
         if (s[i] != s[j])
            min_replacements++;
         i++;
         j--;
      }
      left++;
      right++;
   }
   return min_replacements;
}

int main() {
   string input_string = "abcxyzuvw"; // Replace this with your desired input string
   int k = 3; // Replace this with the desired value of K
   int result = minReplacementsForPalindrome(input_string, k);
   cout << "Minimum replacements required: " << result << endl;
   return 0;
}

Output

Minimum replacements required: 7

Kesimpulan

Artikel ini meneroka masalah bilangan minimum aksara untuk menukar rentetan tertentu kepada subrentetan palindrom dengan panjang K. Ia mengkaji dua kaedah asas untuk menyelesaikan masalah ini: kaedah kekerasan dan kaedah tetingkap gelongsor. Kaedah brute force terdiri daripada memeriksa semua subrentetan panjang K yang mungkin dalam rentetan tertentu, menentukan sama ada ia palindrom, dan menyemak penggantian yang diperlukan. Walau bagaimanapun, pendekatan ini mempunyai kerumitan yang tinggi dan tidak cekap untuk rentetan besar

Sebaliknya, pendekatan tetingkap gelongsor mengoptimumkan kaedah ini dengan mengekalkan tetingkap saiz tetap dan mengemas kini tetingkap dengan cekap semasa menavigasi rentetan input. Artikel ini menyediakan ujian dan pengalaman kod untuk membantu pengguna memahami dan menyelesaikan masalah pemprosesan rentetan yang serupa dengan lebih berjaya.

Atas ialah kandungan terperinci Bilangan minimum aksara yang perlu diganti supaya rentetan itu disatukan menjadi rentetan palindrom dengan panjang K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!