最长公共子串,题目描述:a b两个字符串,求a b的最长公共子串长度,输出最长公共子串长度。子串与子序列不同,子串必须是连续的,而子序列可以不连续。求python代码
时间: 2024-03-23 11:44:00 浏览: 17
好的,以下是Python代码实现:
```python
def longest_common_substring(a, b):
m, n = len(a), len(b)
# 初始化dp数组
dp = [[0] * (n+1) for _ in range(m+1)]
# 初始化最长公共子串长度
max_len = 0
# 遍历a和b的每个字符
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
```
其中,a和b分别表示输入的两个字符串。使用双重循环遍历a和b的每个字符,并根据定义的dp数组进行动态规划。最后返回最长公共子串长度即可。
相关问题
最长公共子串,题目描述: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两个字符串,求ab的最长公共子串长度,输出最长公共子串长度。子串与子序列不同,子串必须是连续的,而子序列可以不连续。用python
好的,这道题目可以使用动态规划的思想,具体实现如下:
```python
a = input() # 读入字符串a
b = input() # 读入字符串b
# 初始化动态规划矩阵
dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]
max_len = 0 # 记录最长公共子串长度
# 动态规划
for i in range(1, len(a)+1):
for j in range(1, len(b)+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
print(max_len) # 输出最长公共子串长度
```
以上代码实现了读入字符串a和字符串b,求它们的最长公共子串长度,并输出最长公共子串长度。