Re^4: True Brute Force Longest Common Sub Sequence

Even with the optimized common, said nasty embedded loops *are there* overall and the using the optimized common doesn't affect the overall complexity.

Actually in the optimised version there are no nested loops and the overall complexity is greatly reduced. The non-optimised version certainly has embedded loops but as you show in the optimised version there is not any need for them because you are using a hash.

Comment on Re^4: True Brute Force Longest Common Sub Sequence

Replies are listed 'Best First'.
Re^5: True Brute Force Longest Common Sub Sequence by ikegami (Patriarch) on Nov 26, 2007 at 06:35 UTC
~~I strongly disagree. Not only does the optimized `common` still requires the nested loops to find the LCS, worse/average O(N^2M^2 + M+N + M+N) is still O(N^2M^2).~~	[reply] [d/l]
Re^6: True Brute Force Longest Common Sub Sequence by tachyon-II (Chaplain) on Nov 28, 2007 at 00:06 UTC
You are of course free to strongly disagree, however it is a matter of fact. Don't take my word for it, insert a loop counter variable and check the results.	[reply]
Re^7: True Brute Force Longest Common Sub Sequence by ikegami (Patriarch) on Nov 28, 2007 at 01:13 UTC
Counters don't show complexity. However, I do see I was wrong. For some odd reason, I was thinking the product of the two sets of subsets had already been found before `common`.	[reply] [d/l]