ali-ghanbari commented on a change in pull request #233:
URL: https://github.com/apache/commons-text/pull/233#discussion_r674459379
##########
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>.
Review comment:
> ... a comment to the array so we don't accidentally make it public.
How about checking the input sizes before invoking althorithmB? As @kinow
mentioned, in that case we have to make sure that the method is not public so
as to avoid malfunctioning of the method. I think it is a good idea to leave
the implementation as it is and just check the input sizes before calling the
method. Please see the newest implementation and share your ideas.
> I think the paper uses K, any reason why dp instead of k (I guess K would
upset Java linters)
Yes, the paper uses notation that might be considered problematic for this
code-base. To avoid confusion, I renamed the variable to "dpRows," which is
what it is (it is two rows of the DP table in the traditional algorithm).
--
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
