最长公共子串动态规划伪代码
时间: 2023-06-28 19:15:47 浏览: 59
以下是最长公共子串的动态规划伪代码实现:
```
function longestCommonSubstring(S1, S2):
m = length(S1)
n = length(S2)
maxLen = 0
endIdx = 0
dp = initialize a m+1 x n+1 matrix with all zeros
for i from 1 to m:
for j from 1 to n:
if S1[i-1] == S2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > maxLen:
maxLen = dp[i][j]
endIdx = i
else:
dp[i][j] = 0
return substring of S1 from endIdx-maxLen to endIdx-1
```
动态规划实现与普通实现的区别在于,dp 数组的大小为 m+1 x n+1,因为需要考虑长度为 0 的子串的情况。同时,dp[i][j] 表示以 S1[i-1] 和 S2[j-1] 结尾的最长公共子串长度,子串的长度可以从 dp 数组中得到。
相关问题
最长公共子串伪代码
以下是最长公共子串的伪代码实现:
```
function longestCommonSubstring(S1, S2):
m = length(S1)
n = length(S2)
maxLen = 0
endIdx = 0
dp = initialize a m x n matrix with all zeros
for i from 1 to m:
for j from 1 to n:
if S1[i-1] == S2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > maxLen:
maxLen = dp[i][j]
endIdx = i
else:
dp[i][j] = 0
return substring of S1 from endIdx-maxLen to endIdx-1
```
其中,dp[i][j] 表示以 S1[i-1] 和 S2[j-1] 结尾的最长公共子串长度,maxLen 表示最长公共子串的长度,endIdx 表示最长公共子串在 S1 中的结束位置,initialize a m x n matrix with all zeros 表示将二维数组初始化为全零矩阵。最后返回最长公共子串在 S1 中的子串。
用伪代码实现最长公共子串
以下是一种求解最长公共子串的伪代码:
```
function longestCommonSubstring(string1, string2)
longestSubstringLength = 0
for i in range(length(string1)):
for j in range(length(string2)):
if string1[i] == string2[j]:
length = 1
while (i + length < length(string1)) and (j + length < length(string2)) and (string1[i+length] == string2[j+length]):
length += 1
if length > longestSubstringLength:
longestSubstringLength = length
longestSubstring = substring(string1, i, i+length)
return longestSubstring
```
该算法的基本思想是枚举字符串1和字符串2的所有子串,然后依次比较它们的字符。如果两个子串的第一个字符相同,则继续比较它们的下一个字符,直到找到不同的字符为止。如果当前的子串长度比之前找到的最长公共子串长度还长,则更新最长公共子串。最后返回最长公共子串。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)