A linear space algorithm for the LCS problem |
| |
| Authors: | S Kiran Kumar C Pandu Rangan |
| |
| Affiliation: | (1) Department of Computer Science and Engineering, Indian Institute of Technology, 600036 Madras, India;(2) Present address: Department of Computer Sciences, University of Texas at Austin, 78712 Austin, Texas, USA |
| |
| Abstract: | Summary The LCS problem is to determine the longest common subsequence (LCS) of two strings. A new linear-space algorithm to solve the LCS problem is presented. The only other algorithm with linear-space complexity is by Hirschberg and has runtime complexity O(mn). Our algorithm, based on the divide and conquer technique, has runtime complexity O(n(m-p)), where p is the length of the LCS. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
