如何加快最长公共子串长度的计算？
Laz*_*zer 6 c++ algorithm dynamic-programming suffix-tree lcs
我有两个非常大的字符串,我试图找出他们的最长公共子串.
一种方法是使用后缀树(假设具有非常好的复杂性,虽然是复杂的实现),另一种方法是动态编程方法(两者都在上面链接的维基百科页面上提到).
使用动态编程
问题是动态编程方法具有巨大的运行时间(复杂性是O(n*m),两个字符串的位置n和m长度).
我想知道的(在跳转到实现后缀树之前):如果我只想知道公共子串的长度(而不是公共子串本身),是否可以加速算法？
实践中会更快吗？是的。Big-Oh 会更快吗？不会。动态规划的解始终是 O(n*m)。
使用后缀树可能会遇到的问题是，您用后缀树的线性时间扫描换取了巨大的空间损失。后缀树通常比您需要为算法的动态编程版本实现的表大得多。根据字符串的长度，动态编程完全有可能会更快。
祝你好运 ：）
- @Billy ONeal：您在比较后缀树和动态规划吗？我不是这么要求的。“我要知道的是，如果我只想知道公共子串的长度，有没有办法使动态规划算法更快？” (2认同)