Hua
BAN USERI thought the question is to find the longest common subsequence between any two users, since the answer in example here is sequence A, C, C which only users 186 and 187 visited.
In the question, it is to find subsequence "from all users". And answer to the example is A, C. it's even better. The only change to the my solution is at step 2, compare the value of the first key in hashtable with the value of the second key. get the LCS and compare with the value of the next key, repeat this getting LCS, and comparing it with next key's value, until done with the hashtable traversal.
i.e.
186: A, C, C, B, A
187: B, A, C, C
188: B, A, C
189: A, D, B, A, C
LCS(ACCBA, BACC) = ACC
LCS( ACC, BAC) = AC
LCS( AC, ADBAC) = AC
resut: AC.
The total time complexity is n.
If you take a look at Completed LCS Table in worked example section on wiki, you will see, to compute the values in current row, what's really needed is the last row.
- Hua January 22, 2013I think suffix trees will also do the work, but it uses space alot.