【问题描述】 最长公共子串,题目描述:a b两个字符串,求a b的最长公共子串长度,输出最长公共子串长度。子串与子序列不同,子串必须是连续的,而子序列可以不连续。 【输入形式】 分两行输入两个字符串 【输出形式】 一行输出长度 【样例输入】 abcccabccsccs abcabcabccs 【样例输出】 6 【样例说明】 【评分标准】 a = input() b = input() la = len(a) lb = len(b) #建立二维列表,行数la+1,列数lb+1,初值为0 res = lc = [] mmax = 0 for i in range(1, la+1): for j in range(1, lb+1): if a[i-1] == b[j-1]: res[i][j] = res[i-1][j-1] + 1 if( ): mmax = res[i][j] print(mmax)补充代码
时间: 2024-02-14 21:36:09 浏览: 20
a = input()
b = input()
la = len(a)
lb = len(b)
# 建立二维列表,行数la+1,列数lb+1,初值为0
res = [[0]*(lb+1) for i in range(la+1)]
mmax = 0
for i in range(1, la+1):
for j in range(1, lb+1):
if a[i-1] == b[j-1]:
res[i][j] = res[i-1][j-1] + 1
if res[i][j] > mmax:
mmax = res[i][j]
print(mmax)
相关问题
最长公共子串,题目描述:a b两个字符串,求a b的最长公共子串长度,输出最长公共子串长度
好的,这是一道经典的字符串算法题目。最长公共子串问题可以通过动态规划的方式求解,具体思路如下:
设 $dp[i][j]$ 表示以 $a[i]$、$b[j]$ 结尾的最长公共子串长度,即:
$$
dp[i][j] = \begin{cases} 0, & i=0 \text{ 或 } j=0 \\ dp[i-1][j-1]+1, & a[i]=b[j] \\ 0, & a[i] \neq b[j] \end{cases}
$$
其中,当 $a[i]=b[j]$ 时,$dp[i][j]$ 取决于 $dp[i-1][j-1]$,表示此时最长公共子串长度加一;当 $a[i]\neq b[j]$ 时,$dp[i][j]$ 必然为零,因为以 $a[i]$、$b[j]$ 结尾的字符串不可能存在公共子串。
最终答案即为 $dp$ 数组中的最大值。时间复杂度为 $O(n^2)$,其中 $n$ 是字符串长度。
代码如下:
最长公共子串,题目描述:a b两个字符串,求a b的最长公共子串长度,输出最长公共子串长度。子串与子序列不同,子串必须是连续的,而子序列可以不连续。
好的,这道题目需要求解的是最长公共子串问题,与最长公共子序列问题有所不同。最长公共子串问题可以通过动态规划的方式求解,具体思路如下:
设 $dp[i][j]$ 表示以 $a[i]$、$b[j]$ 结尾的最长公共子串长度,即:
$$
dp[i][j] = \begin{cases} 0, & i=0 \text{ 或 } j=0 \\ dp[i-1][j-1]+1, & a[i]=b[j] \\ 0, & a[i] \neq b[j] \end{cases}
$$
其中,当 $a[i]=b[j]$ 时,$dp[i][j]$ 取决于 $dp[i-1][j-1]$,表示此时最长公共子串长度加一;当 $a[i]\neq b[j]$ 时,$dp[i][j]$ 必然为零,因为以 $a[i]$、$b[j]$ 结尾的字符串不可能存在公共子串。
最终答案即为 $dp$ 数组中的最大值。时间复杂度为 $O(n^2)$,其中 $n$ 是字符串长度。
代码如下:
```python
def longest_common_substring(a, b):
m, n = len(a), len(b)
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 a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
else:
dp[i][j] = 0
return max_len
```
如果需要输出最长公共子串,可以记录最长公共子串的结束位置,然后通过结束位置和最长公共子串长度计算出起始位置:
```python
def longest_common_substring(a, b):
m, n = len(a), len(b)
dp = [[0] * (n+1) for _ in range(m+1)]
end, max_len = 0, 0
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end = i - 1
else:
dp[i][j] = 0
start = end - max_len + 1
return a[start:end+1]
```
相关推荐
![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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)