URN 
etd0811117153330 
Author 
BiShiang Lin 
Author's Email Address 
No Public. 
Statistics 
This thesis had been viewed 5340 times. Download 22 times. 
Department 
Computer Science and Engineering 
Year 
2017 
Semester 
1 
Degree 
Master 
Type of Document 

Language 
English 
Title 
The Algorithms for the Linear Space Stable on the Longest Common Subsequence Problem 
Date of Defense 
20170912 
Page Count 
60 
Keyword 
longest common subsequence
consecutive suffix alignment problem
linear space
Stable
range query
segment tree

Abstract 
Given two sequences A and B of lengths m and n, respectively, the consecutive suffix alignment problem is to compute the longest common subsequence (LCS) between A and each suffix of B. The data structure for the consecutive suffix alignment problem is named Stable, which is a twodimensional matrix. The Stable of A(r) and B can be used to compute the LCS with the concatenation of two substrings (A(r1) and A(r)) and B in O(L) time, with the alignment result of A(r1) and B is given, where L denotes the LCS length. In this thesis, we focus on the linear space Stable. The linear space Stable was fi rst proposed by Alves et al., but without further discussions and practical applications. We propose an algorithm to compute the LCS of two concatenated strings and one string in O(n) time by using the linear space Stable. We also propose an algorithm for merging two linear Stables in O(n log n) time, instead of merging two Stable in quadratic time previously. At last, we propose an algorithm to compute the linear space Stable of A and B with given the linear space Stable of A and B in O(n) time, where denotes a new character appended to the tail of A. 
Advisory Committee 
HsingYen Ann  chair
YungHsing Peng  cochair
KuoTsung Tseng  cochair
KuoSi Huang  cochair
ChangBiau Yang  advisor

Files 
Indicate incampus at 0 year and offcampus access at 1 year. 
Date of Submission 
20170912 