| java.lang.Object
 org.eclipse.compare.internal.LCS
All known Subclasses: org.eclipse.compare.rangedifferencer.RangeComparatorLCS,
| LCS | | abstract public class LCS (Code) | | |
| getLength | | public int getLength()(Code) | | |
| getLength1 | | abstract protected int getLength1()(Code) | | |
| getLength2 | | abstract protected int getLength2()(Code) | | |
| initializeLcs | | abstract protected void initializeLcs(int lcsLength)(Code) | | |
| isRangeEqual | | abstract protected boolean isRangeEqual(int i1, int i2)(Code) | | |
| longestCommonSubsequence | | public void longestCommonSubsequence(SubMonitor subMonitor, LCSSettings settings)(Code) | | Myers' algorithm for longest common subsequence. O((M + N)D) worst
case time, O(M + N + D^2) expected time, O(M + N) space
(http://citeseer.ist.psu.edu/myers86ond.html)
Note: Beyond implementing the algorithm as described in the paper I
have added diagonal range compression which helps when finding the
LCS of a very long and a very short sequence, also bound the running
time to (N + M)^1.5 when both sequences are very long.
After this method is called, the longest common subsequence is
available by calling getResult() where result[0] is composed of
entries from l1 and result[1] is composed of entries from l2
Parameters:
subMonitor - |
| setLcs | | abstract protected void setLcs(int sl1, int sl2)(Code) | | |
|
|