使一個字串等於另一個字串所需刪除的最長子字串的長度

在本文中，我們將討論找到需要刪除的最長子字串的長度以使一個字串等於另一個字串的問題。我們將首先理解問題陳述，然後探索解決問題的簡單和有效的方法，以及它們各自的演算法和時間複雜度。最後，我們將用 C 實作該解決方案。

問題陳述

給定兩個字串 A 和 B，確定需要從字串 A 中刪除的最長子字串的長度，使其等於字串 B。

天真的方法

最簡單的方法是產生字串 A 的所有可能的子字串，將它們一一刪除，然後檢查結果字串是否等於字串 B。如果是，我們將儲存刪除的子字串的長度。最後，我們將傳回所有刪除的子字串中的最大長度。

演算法（樸素）

• 將 maxLength 初始化為 0。

• 產生字串A的所有可能的子字串

• 對於每個子字串，將其從字串 A 中刪除，並檢查結果字串是否等於字串 B。

• 如果是，則將maxLength更新為maxLength與刪除子字串長度中的最大值。

• 傳回最大長度。

C 程式碼（樸素）

範例

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

輸出

Length of longest substring to be deleted: 1

時間複雜度（樸素） - O(n^3)，其中 n 是字串 A 的長度。

高效的方法

解決這個問題的有效方法是找到兩個字串的最長公共子序列（LCS）。字串A中需要刪除的最長子字串的長度，使其等於字串B，其長度就是字串A的長度與LCS長度的差。

演算法（高效）

• 找出字串 A 和字串 B 的最長公共子序列 (LCS)。

• 傳回字串A的長度與LCS的長度之間的差。

C 程式碼（高效率）

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

輸出

Length of longest substring to be deleted: 1

時間複雜度（高效） - O(m * n)，其中 m 是字串 A 的長度，n 是字串 B 的長度。

結論

在本文中，我們探討了尋找需要刪除的最長子字串的長度以使一個字串等於另一個字串的問題。我們討論了解決這個問題的簡單而有效的方法，以及它們的演算法和時間複雜度。高效方法利用最長公共子序列概念，與樸素方法相比，時間複雜度有了顯著提高。

以上是使一個字串等於另一個字串所需刪除的最長子字串的長度的詳細內容。更多資訊請關注PHP中文網其他相關文章！