| Autor: |
Ratul Bhowmick, Ahsan Sadee Tanim, Muhammad Kamal Hossen, Md. Sabir Hossain, Ibrahim Sadek Bhuiyan |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
2019 1st International Conference on Advances in Science, Engineering and Robotics Technology (ICASERT). |
| DOI: |
10.1109/icasert.2019.8934638 |
| Popis: |
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). |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
