ali-ghanbari commented on a change in pull request #233:
URL: https://github.com/apache/commons-text/pull/233#discussion_r674457294
##########
File path:
src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
##########
@@ -58,7 +58,57 @@ public Integer apply(final CharSequence left, final
CharSequence right) {
if (left == null || right == null) {
throw new IllegalArgumentException("Inputs must not be null");
}
- return longestCommonSubsequence(left, right).length();
+ // Find lengths of two strings
+ final int leftSz = left.length();
+ final int rightSz = right.length();
+
+ // Check if we can save even more space
+ if (leftSz < rightSz) {
+ return algorithmB(right, rightSz, left, leftSz)[leftSz];
+ }
+ return algorithmB(left, leftSz, right, rightSz)[rightSz];
+ }
+
+ /**
+ * An implementation of "ALG B" from Hirschberg's paper <a
href="https://dl.acm.org/doi/10.1145/360825.360861";>A linear space algorithm
for computing maximal common subsequences</a>.
+ * Assuming the sequence <code>left</code> is of size <code>m</code> and
the sequence <code>right</code> is of size <code>n</code>,
+ * this method returns the last row of the dynamic programming table when
calculating LCS the two sequences.
+ * Therefore, the last element of the returned array, is the size of LCS
of <code>left</code> and <code>right</code>.
+ * This method runs in O(m * n) time and O(n) space.
+ * To save more space, it is preferable to pass the shorter sequence as
<code>right</code>.
+ *
+ * @param left Left sequence
+ * @param m Length of left sequence
+ * @param right Right sequence
+ * @param n Length of right sequence
+ * @return Last row of DP table for calculating LCS of <code>left</code>
and <code>right</code>
+ */
+ static int[] algorithmB(final CharSequence left, final int m,
Review comment:
Yes, that's the idea! ;)
The traditional LCS algorithms are variants of Algorithm A in the paper.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
