数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告