Hacker News Reader

What 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_prob...

I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing

View on HN

Can 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.

Indeed, 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.

Reply on news.ycombinator.com