資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究刪除最長子字串以使字串等於另一個字串
在本文中，我們將討論查詢需要刪除的最長子字串以使一個字串等於另一個字串的問題。我們將首先了解問題陳述，然後探索解決此問題的樸素和有效方法，以及它們各自的演算法和時間複雜度。最後，我們將實現解決方案。
問題陳述
給定兩個字串 A 和 B，確定需要從字串 A 中刪除的最長子字串的長度，以使其等於字串 B。
樸素方法
樸素方法是生成字串 A 的所有可能的子字串，逐個刪除每個子字串，並檢查結果字串是否等於字串 B。如果是，我們將儲存已刪除子字串的長度。最後，我們將返回所有已刪除子字串中的最大長度。
演算法（樸素）
將 maxLength 初始化為 0。
生成字串 A 的所有可能的子字串
對於每個子字串，將其從字串 A 中刪除，並檢查結果字串是否等於字串 B。
如果是，則將 maxLength 更新為 maxLength 和已刪除子字串長度中的最大值。
返回 maxLength。
程式碼（樸素）
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <string.h>
int longestSubstringToDelete(char A[], char B[]) {
int maxLength = 0;
for (int i = 0; i < strlen(A); i++) {
for (int j = i; j < strlen(A); j++) {
// Create a temporary string and remove the substring from i to j
char temp[strlen(A) + 1];
strcpy(temp, A);
memmove(temp + i, temp + j + 1, strlen(temp) - j);
// Compare the temporary string with string B
if (strcmp(temp, B) == 0) {
maxLength = (j - i + 1 > maxLength) ? j - i + 1 : maxLength;
}
}
}
return maxLength;
}
int main() {
char A[] = "abcde";
char B[] = "acde";
printf("Length of longest substring to be deleted: %d\n", longestSubstringToDelete(A, B));
return 0;
}
輸出
Length of longest substring to be deleted: 1
#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
public class Main {
public static int longestSubstringToDelete(String A, String B) {
int maxLength = 0;
for (int i = 0; i < A.length(); i++) {
for (int j = i; j < A.length(); j++) {
// Create a temporary StringBuilder and remove the substring from i to j
StringBuilder temp = new StringBuilder(A);
temp.delete(i, j + 1);
// Compare the temporary StringBuilder with string B
if (temp.toString().equals(B)) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}
public static void main(String[] args) {
String A = "abcde";
String B = "acde";
System.out.println("Length of longest substring to be deleted: " + longestSubstringToDelete(A, B));
}
}
輸出
Length of longest substring to be deleted: 1
def longest_substring_to_delete(A, B):
max_length = 0
for i in range(len(A)):
for j in range(i, len(A)):
# Create a temporary string and remove the substring from i to j
temp = A[:i] + A[j+1:]
# Compare the temporary string with string B
if temp == B:
max_length = max(max_length, j - i + 1)
return max_length
def main():
A = "abcde"
B = "acde"
print("Length of longest substring to be deleted:", longest_substring_to_delete(A, B))
if __name__ == "__main__":
main()
輸出
Length of longest substring to be deleted: 1
時間複雜度（樸素） - O(n^3)，其中 n 是字串 A 的長度。
有效方法
解決此問題的有效方法是找到兩個字串的最長公共子序列 (LCS)。需要從字串 A 中刪除的最長子字串的長度是字串 A 的長度與 LCS 的長度之差。
演算法（有效）
找到字串 A 和字串 B 的最長公共子序列 (LCS)。
返回字串 A 的長度與 LCS 的長度之差。
程式碼（有效）
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Function to calculate longest common subsequence
int longestCommonSubsequence(char A[], char B[]) {
int m = strlen(A);
int n = strlen(B);
// Create a 2D array to store LCS lengths
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0; // Initialize all values to 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] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
return dp[m][n];
}
// Function to calculate length of longest substring to be deleted
int longestSubstringToDelete(char A[], char B[]) {
int lcsLength = longestCommonSubsequence(A, B);
return strlen(A) - lcsLength;
}
int main() {
char A[] = "abcde";
char B[] = "acde";
printf("Length of longest substring to be deleted: %d\n", longestSubstringToDelete(A, B));
return 0;
}
輸出
Length of longest substring to be deleted: 1
#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
public class Main {
public static int longestCommonSubsequence(String A, String B) {
int m = A.length();
int n = B.length();
// Create a 2D array to store LCS lengths
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
public static int longestSubstringToDelete(String A, String B) {
int lcsLength = longestCommonSubsequence(A, B);
return A.length() - lcsLength;
}
public static void main(String[] args) {
String A = "abcde";
String B = "acde";
System.out.println("Length of longest substring to be deleted: " + longestSubstringToDelete(A, B));
}
}
輸出
Length of longest substring to be deleted: 1
def longest_common_subsequence(A, B):
m = len(A)
n = len(B)
# Create a 2D list to store LCS lengths
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if A[i - 1] == B[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def longest_substring_to_delete(A, B):
lcs_length = longest_common_subsequence(A, B)
return len(A) - lcs_length
def main():
A = "abcde"
B = "acde"
print("Length of longest substring to be deleted:", longest_substring_to_delete(A, B))
if __name__ == "__main__":
main()
輸出
Length of longest substring to be deleted: 1
時間複雜度（有效） - O(m * n)，其中 m 是字串 A 的長度，n 是字串 B 的長度。
結論
在本文中，我們探討了查詢需要刪除的最長子字串以使一個字串等於另一個字串的問題。我們討論瞭解決此問題的樸素和有效方法，以及它們的演算法和時間複雜度。有效方法利用最長公共子序列的概念，與樸素方法相比，在時間複雜度方面有了顯著的提高。
更新於：2023年10月23日
154 次瀏覽
廣告