ggyuchive opened a new issue, #3314: URL: https://github.com/apache/kvrocks/issues/3314
### Search before asking - [x] I had searched in the [issues](https://github.com/apache/kvrocks/issues) and found no similar issues. ### Motivation In kvrocks LCS command, it uses Dynamic Programming. When two string S, T and get LCS(S, T), - Time Complexity: O(|S||T|) - Space Complexity: O(|S||T|) When |S| and |T| is about 10000, it requires over 400MB. ### Solution We can reduce space complexity to O(|S|+|T|) using Hirschberg's algorithm, also it can recover LCS string. Relevant paper: A Linear Space Algorithm for Computing Maximal Common Subsequences (Author: D.S. Hirschberg) ### Are you willing to submit a PR? - [x] I'm willing to submit a PR! -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
