URN 
etd0827106160715 
Author 
ChiouTing Tseng 
Author's Email Address 
M923040003@student.nsysu.edu.tw 
Statistics 
This thesis had been viewed 5350 times. Download 1261 times. 
Department 
Computer Science and Engineering 
Year 
2005 
Semester 
2 
Degree 
Master 
Type of Document 

Language 
English 
Title 
Finding the Longest Increasing Subsequence of Every Substring 
Date of Defense 
20060706 
Page Count 
43 
Keyword 
longest increasing subsequence
row tower
substring
sliding window

Abstract 
Given a string S = {a1, a2, a3, ..., an}, the longest increasing subsequence (LIS) problem is to find a subsequence of the given string such that the subsequence is increasing and its length is maximal. In a previous result, to find the longest increasing subsequences of each sliding window with a fixed size w of a given string with length n can be solved in O(w log log n+OUTPUT) time, where O(w log log n+ w^2) time is taken for preprocessing and OUTPUT is the sum of all output lengths. In this thesis, we solve the problem for finding the longest increasing subsequence of every substring of S. With the straightforward implementation of the previous result, the time required for the preprocessing would be O(n^3). We modify the data structure used in the algorithm, hence the required preprocessing time is improved to O(n^2). The time required for the report stage is linear to the size of the output. In other words, our algorithm can find the LIS of every substring in O(n^2+OUTPUT) time. If the LIS's of all substrings are desired to be reported, since there are O(n^2) substrings totally in a given string with length n, our algorithm is optimal. 
Advisory Committee 
ShiJinn Horng  chair
YiHsing Chang  cochair
Yueli Wang  cochair
ChiaPing Chen  cochair
ChangBiau Yang  advisor

Files 
indicate incampus access immediately and off_campus access in a year 
Date of Submission 
20060827 