常见的子串算法:
LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
else 0
现在动态编程解决方案已经很好理解了 . 但是我无法弄清楚递归解决方案 . 如果有多个子串,则上述算法似乎失败 .
例如:
x = "LABFQDB" and y = "LABDB"
应用上述算法
1+ (x= "LABFQD" and y = "LABD")
1+ (x= "LABFQ" and y = "LAB")
return 0 since 'Q'!='B'
返回的值是2,我应该是3?
有人可以指定递归解决方案吗?
4 回答
您不理解该算法,因为它不是最长公共子串的算法...
正确的公式是:
包algo.dynamic;
public class LongestCommonSubstring {
}
problem 与你的代码似乎你没有尝试所有n ^ 2的可能性 .
我在c中为此设计了一个递归解决方案 . 在我的方法中我采取一个特定的i,j,然后如果他们是相等的我加1并调用函数为i 1,j 1,而如果他们不相等我在相应的i,j存储零在我创建的2D数组中 . 执行后我打印2D数组,似乎没问题 . 因为我只是填充2D数组,我认为时间复杂度必须是O(mn),其中m是一个数组的长度,n是另一个数组 .