This week I've implemented an algorithm to show difference between two texts.
I've implement the LCS(Longest Common Sequence) algotithm. The Longest Common Sequence consist is finding the longest subsequence common to all sequences in a set of sequences. It is a NP-Hard problem but can be solved in psedo-polynomial time using dynamic programming.
But what LCS algorithm can be used on diff problem?
The best diff result is the set with less common sequence between two sets. And, LCS can find the longest common subsequence. With LCS result, we can compare to two input sets and check what was add and what was removed, finding a solution. But this last comparison is not necessary, using the matrix built with dynamic programming, it is possible to find the the diff solution.
There's an optimization for my code, but I'll do it later. First, I need to make thinks work.
I have implemented these functions separately. Now I will integrate to Joomla!