This thesis considers a variant of the classical problem for finding the longest common subsequence (LCS) called longest common subsequence problem with a gapped constraint (LCSGC). Given two sequences A, B, and a constrained sequence C, which is accomplished with a corresponding gapped constraint for each symbol, whose lengths are m, n, and r, respectively, the LCSGC problem is to find an LCS of A and B, such that C is also a subsequence of this LCS and the gapped constraints corresponding to C are satisfied. In this thesis, two algorithms with time complexities O(m2n2r) and O(mnr ¡Ñ min(m, n)) are proposed based on the dynamic programming technique for solving the LCSGC problem.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0912112-090312 |
| Date | 12 September 2012 |
| Creators | Cheng, Kai-Yuan |
| Contributors | Chang-Biau Yang, Hsing-Yen Ann, Kuo-Si Huang, Yung-Hsing Peng, Chung-Nan Lee |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0912112-090312 |
| Rights | user_define, Copyright information available at source archive |
Page generated in 0.0023 seconds