子序列和子串有什么区别
时间: 2023-03-30 11:02:50 浏览: 148
子序列和子串的区别在于子序列可以不连续,而子串必须是连续的一段。例如,字符串"abcd"的子序列有"a", "b", "c", "d", "ab", "ac", "ad", "bc", "bd", "cd", "abc", "abd", "acd", "bcd", "abcd",而子串只有"a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd", "d"。
相关问题
最长公共子序列和最长公共子串(python)
最长公共子序列(Longest Common Subsequence, LCS)和最长公共子串(Longest Common Substring)是两个常见的字符串相关问题。
最长公共子序列是指给定两个字符串,要求找到它们之间最长的公共子序列的长度。子序列是从原字符串中删除若干个字符而得到的新字符串,字符在新字符串中的相对顺序与原字符串中的保持一致。动态规划是求解LCS问题的常用方法。
以字符串s1 = "ABCBDAB"和s2 = "BDCAB"为例,可以使用动态规划的方法求解最长公共子序列的长度。首先创建一个二维数组dp,dp[i][j]表示s1的前i个字符和s2的前j个字符之间的最长公共子序列的长度,那么有以下推导关系:
1. 当i=0或j=0时,dp[i][j]=0。
2. 当s1[i-1]=s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1。
3. 当s1[i-1]!=s2[j-1]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最后,dp[len(s1)][len(s2)]即为最长公共子序列的长度。
对于最长公共子串,要求找到两个字符串中最长的公共连续子串的长度。连续子串是指在原字符串中连续出现的字符子序列。同样可以使用动态规划来解决该问题。
仍以上述两个字符串s1和s2为例,创建一个二维数组dp,dp[i][j]表示以s1[i-1]和s2[j-1]为结尾的公共子串的长度,那么有以下推导关系:
1. 当i=0或j=0时,dp[i][j]=0。
2. 当s1[i-1]=s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1。
3. 当s1[i-1]!=s2[j-1]时,dp[i][j] = 0。
最后,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$ 是字符串长度。
代码如下:
```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]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)