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

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

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