An Approach for Improving Complexity of Longest Common Subsequence Problems using Queue and Divide-and-Conquer Method
Ratul Bhowmick, Md Ibrahim Sadek Bhuiyan, Md. Sabir Hossain, Muhammad Kamal Hossen, Ahsan Sadee Tanim · 2019 1st International Conference on Advances in Science, Engineering and Robotics Technology (ICASERT) · 2019
The general algorithms which are followed to solve the Longest Common Subsequence (LCS) problems have both time complexity and space complexity of O(m * n). To reduce this complexity, two ways are proposed in this work. One is the use of Divide and Conquer approach, and another one is changing the data structure from two-dimensional array to queue. By using these approaches, an algorithm has been developed and implemented for the long length string in this paper. The time complexity after using these approaches becomes a function of logarithm O(n * log(n)) which has been shown with proper explanation and the space complexity after using queue data structure becomes linear O(n).