Panjang subrentetan terpanjang yang perlu dibuang untuk menjadikan satu rentetan sama dengan rentetan lain

Dalam artikel ini, kita akan membincangkan masalah mencari panjang substring terpanjang yang perlu dibuang untuk menjadikan satu rentetan sama dengan rentetan yang lain. Kami mula-mula akan memahami penyataan masalah dan kemudian meneroka cara yang mudah dan cekap untuk menyelesaikan masalah, bersama-sama dengan kerumitan algoritma dan masa masing-masing. Akhirnya, kami akan melaksanakan penyelesaian dalam C++.

Pernyataan Masalah

Diberi dua rentetan A dan B, tentukan panjang subrentetan terpanjang yang perlu dikeluarkan daripada rentetan A supaya ia sama dengan rentetan B.

Kaedah naif

Cara paling mudah ialah menjana semua subrentetan yang mungkin bagi rentetan A, keluarkannya satu demi satu, dan kemudian semak sama ada rentetan yang terhasil adalah sama dengan rentetan B. Jika ya, kami menyimpan panjang subrentetan yang dikeluarkan. Akhir sekali, kami akan mengembalikan panjang maksimum antara semua subrentetan yang dialih keluar.

Algoritma (naif)

• Awalkan maxLength kepada 0.

• Janakan semua kemungkinan subrentetan rentetan A

• Untuk setiap subrentetan, keluarkan ia daripada rentetan A dan semak sama ada rentetan yang terhasil adalah sama dengan rentetan B.

• Jika ya, kemas kini maxLength kepada nilai maksimum maxLength dan padamkan panjang substring.

• Kembalikan panjang maksimum.

Kod C++ (biasa)

Contoh

#include <iostream>
#include <string>
#include <algorithm>

int longestSubstringToDelete(std::string A, std::string B) {
   int maxLength = 0;
   
   for (int i = 0; i < A.length(); i++) {
      for (int j = i; j < A.length(); j++) {
         std::string temp = A;
         temp.erase(i, j - i + 1);
   
         if (temp == B) {
            maxLength = std::max(maxLength, j - i + 1);
         }
      }
   }
   
   return maxLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}

Output

Length of longest substring to be deleted: 1

Kerumitan masa (naif) - O(n^3), dengan n ialah panjang rentetan A.

Kaedah yang cekap

Cara yang cekap untuk menyelesaikan masalah ini ialah mencari urutan sepunya terpanjang (LCS) bagi dua rentetan. Panjang subrentetan terpanjang yang perlu dipadamkan dalam rentetan A supaya sama dengan rentetan B ialah perbezaan antara panjang rentetan A dan panjang LCS.

Algoritma (cekap)

• Cari urutan sepunya terpanjang (LCS) rentetan A dan rentetan B.

• Mengembalikan perbezaan antara panjang tali A dan panjang LCS.

Kod C++ (cekap)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string A, std::string B) {
   int m = A.length();
   int n = B.length();
   std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
   
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (A[i - 1] == B[j - 1]) {
            
            dp[i][j] = 1 + dp[i - 1][j - 1];
         } else {
            dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
         }
      }
   }
   return dp[m][n];
}

int longestSubstringToDelete(std::string A, std::string B) {
   int lcsLength = longestCommonSubsequence(A, B);
   return A.length() - lcsLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}

Output

Length of longest substring to be deleted: 1

Kerumitan masa (cekap) - O(m * n), dengan m ialah panjang rentetan A dan n ialah panjang rentetan B.

Kesimpulan

Dalam artikel ini, kami meneroka masalah mencari panjang subrentetan terpanjang yang perlu dibuang untuk menjadikan satu rentetan sama dengan rentetan yang lain. Kami membincangkan kaedah yang mudah tetapi cekap untuk menyelesaikan masalah ini, bersama-sama dengan kerumitan algoritma dan masa mereka. Kaedah yang cekap mengeksploitasi konsep urutan biasa yang paling lama dan mencapai peningkatan yang ketara dalam kerumitan masa berbanding kaedah naif.

Atas ialah kandungan terperinci Panjang subrentetan terpanjang yang perlu dibuang untuk menjadikan satu rentetan sama dengan rentetan lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!