我找到了Longest Common Substring的算法。通常使用dynamic programming
,使用大小为 的二维数组来完成,mxn
其中m
和n
是所考虑的两个字符串的长度。
我将为这两个字符串构造以下矩阵。
M[i][j] = 1 if s1[i]==s2[j] else 0.
例如,如果字符串是:abcxy
和pqaabx
矩阵如下所示:
a b c x y
p 0 0 0 0 0
q 0 0 0 0 0
a 1 0 0 0 0
a 1 0 0 0 0
b 0 1 0 0 0
x 0 0 0 1 0
1
现在,我在从左上到右下方向的每个对角线中搜索 s 的最大连续序列。
其中的最大值就是答案。
我可以在不显式使用数组的情况下执行上述操作。时间复杂度仍然是O(M*N)
。所以,不需要内存。
谁能指出我哪里出错了?