最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。 输入样例: 1AB2345CD 12345EF 输出样例: 4 说明:最长的公共子串为2345;
时间: 2024-05-16 13:12:27 浏览: 12
可以使用动态规划来解决该问题。定义一个二维数组dp,其中dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子串的长度。则当str1[i-1]和str2[j-1]相同时,dp[i][j]=dp[i-1][j-1]+1;否则,dp[i][j]=0。最后,遍历dp数组找到最大值即可。
Python代码实现如下:
```python
def longest_common_substring(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
max_len = max(max_len, dp[i][j])
return max_len
# 示例
str1 = "1AB2345CD"
str2 = "12345EF"
print(longest_common_substring(str1, str2)) # 输出 4
```
相关问题
最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。
最长公共子串问题可以使用动态规划求解。
定义一个二维数组dp,其中dp[i][j]表示以str1[i]和str2[j]结尾的最长公共子串的长度。如果str1[i]和str2[j]不相等,则dp[i][j]=0;如果相等,则有dp[i][j]=dp[i-1][j-1]+1。
最终的最长公共子串的长度就是dp数组中的最大值。
以下是Python代码实现:
```python
def longest_common_substring(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * n for _ in range(m)]
max_len = 0
for i in range(m):
for j in range(n):
if str1[i] == str2[j]:
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
return max_len
```
例如,对于字符串"abcdefg"和"bcdeff",最长公共子串为"bcdef",长度为5。
用java实现:最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。
以下是用Java实现最长公共子串长度的示例代码:
```java
public class LongestCommonSubstring {
public static int longestCommonSubstring(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int maxLength = 0;
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
public static void main(String[] args) {
String str1 = "abcdxyz";
String str2 = "xyzabcd";
int maxLength = longestCommonSubstring(str1, str2);
System.out.println("The length of longest common substring is " + maxLength);
}
}
```
以上代码使用动态规划算法来解决该问题。通过定义一个二维数组`dp`,其中`dp[i][j]`表示以`str1`的第`i`个字符和`str2`的第`j`个字符为结尾的最长公共子串的长度。当`str1.charAt(i-1) == str2.charAt(j-1)`时,表示`str1`和`str2`的第`i`和`j`个字符相同,因此可以通过`dp[i-1][j-1]`得到以`str1`的第`i-1`个字符和`str2`的第`j-1`个字符为结尾的最长公共子串长度,并加上当前相同的字符,即可得到以`str1`的第`i`个字符和`str2`的第`j`个字符为结尾的最长公共子串的长度。同时,需要记录每次更新的最大长度,并在遍历完成后返回该长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)