41 ms·
The longest common substring problem (LCS) can be solved in O(n^2) time using dynamic programming, not O(n^3) as is stated by the author of that post. If the au
by attractivechaos 15y ago
The longest common substring problem (LCS) can be solved in O(n^2) time using dynamic programming, not O(n^3) as is stated by the author of that post. If the author is unable to get the basic fact right, I can hardly trust his benchmark. Also, I question the author's skill in C/C++: in my experiences, C is consistently faster than Java for such tasks and C++ is nearly as fast as C as long as we use it the right way. If we look at the computer benchmark games, OCaml never beats C in terms of speed. I doubt the conclusion was much different in 2006. The author should released the source code; otherwise the benchmark tells us nothing but his incapability in programming.
EDIT: in his comments to another commenter, the author was saying this: "[The OCaml compiler] could do some dramatic code rewriting that made it possible to merge loops, and hoist some local constants out of the restructured merged loop." A good C programmer should be able to do all the above simply by instinct. The author was not good enough. I buy the argument that being really good at C/C++ is more difficult than at other languages, but this is not the same thing as arguing C is inefficient.
- pandaman 15y agoJudging by the difference in his numbers between C and C++ he did not have a slightest clue of what he was doing. I could imagine a slight difference is possible if you use default compiler switches due to exception handling and difference aliasing rules, not 3x as he has.
- chengl 15y agoWhat the author mentioned is longest common SUBSEQUENCE (not substring). And it's true that LCS requires O(n^2) if only need to find ONE LCS, using dynamic programming. But if it's required to find ALL longest common subsequence, it definitely requires higher order. http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob... I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing
- attractivechaos 15y agoCan you find the proof that finding all LCS is O(n^3)? The author was talking about "the standard algorithm for computing LCS". I was assuming the standard algorithm finds one LCS only.
- cperciva 15y agoIndeed, finding all LCSs requires exponential time: The strings "abcdefghijkl..." and "badcfehgjilk..." have the 2^(N/2) LCSs "[ab][cd][ef][gh][ij][kl]..." and no algorithm can ever run faster than the amount of time it takes to print its output.