最长公共子串伪代码
时间: 2023-07-02 20:12:47 浏览: 59
以下是最长公共子串的伪代码实现:
```
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 中的子串。