Title page for etd-0811117-153330


[Back to Results | New Search]

URN etd-0811117-153330
Author Bi-Shiang 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 S-table on the Longest Common
Subsequence Problem
Date of Defense 2017-09-12
Page Count 60
Keyword
  • longest common subsequence
  • consecutive suffix alignment problem
  • linear space
  • S-table
  • 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 S-table, which is a two-dimensional matrix. The S-table of A(r) and B can be used to compute the LCS with the concatenation of two substrings (A(r-1) and A(r)) and B in O(L) time, with the alignment result of A(r-1) and B is given, where L denotes the LCS length.
    In this thesis, we focus on the linear space S-table. The linear space S-table 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 S-table. We also propose an algorithm for merging two linear S-tables in O(n log n) time, instead of merging two S-table in quadratic time previously. At last, we propose an algorithm to compute the linear space S-table of A and B with given the linear space S-table of A and B in O(n) time, where  denotes a new character appended to the tail of A.
    Advisory Committee
  • Hsing-Yen Ann - chair
  • Yung-Hsing Peng - co-chair
  • Kuo-Tsung Tseng - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0811117-153330.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2017-09-12

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys