# 臺灣博碩士論文加值系統

(18.208.186.139) 您好！臺灣時間：2022/05/29 03:04

:::

### 詳目顯示

:

• 被引用:0
• 點閱:171
• 評分:
• 下載:8
• 書目收藏:0
 給定一字串 ， 被稱為字串 的倒轉。 是ㄧ個非空的字串。字串 被稱為精確迴文，而字串 被稱為間隔迴文。我們這篇論文要解決的問題定義如下：給定一長度為 的字串 ，找尋在字串 中所有的精確迴文及間隔迴文。　　在這篇論文中，我們提出一個基於字尾樹的演算法來解決這個迴文找尋問題。以下是我們演算法的描述：ㄧ開始，我們反轉給定的字串 ，並稱這新的字串為 。我們為這兩字串 及 建造ㄧ字尾數。我們在這字尾數上標定前收集，後收集和 之後，我們提出兩公式來找尋迴文。使用第一個公式 ，我們將找出精確迴文。近一步地，我們使用第二個公式 來找尋間隔迴文。這兩公式是幫助我們解決這迴文找尋問題的主要技巧。
 Given a string , is called the reverse of is a non-empty string. The string is called an exact palindrome and the string is called a gaped palindrome. The problem of the thesis is defined as follows: Given a string of length , find all exact and gaped palindromes in .In the thesis, we propose an algorithm based on suffix trees to solve the problem. The algorithm is described as follows. At the beginning, we reverse the given string and denote the new string as . We construct the suffix tree for and . After labeling the forward collections, backward collections and s on the constructed suffix tree, we propose two formulas to find palindromes. By using the first formula , we will find all exact palindromes. Furthermore, we can find all gaped palindromes by using second formula . The two formulas are the main tricks for helping us to solve the problem.
 List of Figures vList of Tables viChapter 1 Introduction 1-11.1 Motivations and Previous Works 1-11.2 Thesis Organization 1-2Chapter 2 Manacher Algorithm 2-12.1 The Brute Force Algorithm 2-12.2 The Manacher Algorithm 2-32.3 A Full Example of Manacher Algorithm 2-7Chapter 3 Solving the Palindrome Detection Problem Based upon Suffix Trees 3-13.1 Term Definitions 3-13.2 Finding Exact Palindromes 3-63.3 Finding Gaped Palindromes 3-103.4 Full Example for Finding All Palindromes 3-17Chapter 4 Conclusion 4-1Bibliography 5-1
 [A2000] Frequency-Domain Analysis of Biomolecular Sequences, Anastassiou, D., Bioinformatics, Vol. 16, 2000, pp. 1073-1081.[A2001] Genomic Signal Processing, Anastassiou, D., IEEE Signal Processing Magazine, Vol. 18, 2001, pp. 8-20.[B2003] Hypermutable Minisatellites, a Human Affair?, Bois, P. R. J., Genomics, Vol. 81, 2003, pp. 349-355.[B99] Tandem Repeats Finder: a Program to Analyze DNA Sequences, Benson, G., Oxford University Press, Vol. 27, 1999, pp. 573-580.[BJ2003] Detection and Visualization of Tandem Repeats in DNA Sequences, Buchner, M. and Janjarasjitt, S., IEEE Transactions on Signal Processing, Vol. 51, 2003, pp. 2280-2287.[BR2003] Comparison of Minisatellites, Berard, S. and Rivals, E., Journal of Computational Biology, Vol. 10, 2003, pp. 357-372.[C81] An Optimal Algorithm for Computing the Repetitions in a Word, Crochemore, M., Information Processing Letters, Vol. 12, 1981, pp. 244-250.[CR2003] Jewels of Stringology, Crochemore, M. and Rytter, W., World Scientific Publishing Company, 2003.[FS98] How Many Squares Can a String Contain?, Fraenkel, A. S. and Simpson, J., Journal of Combinatorial Theory, Vol. 82, 1998, pp. 112-120.[G97] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Gusfield, D., Cambridge University Press, 1997.[GS2004] Linear Time Algorithms for Finding and Representing All the Tandem Repeats in a String, Gusfield, D. and Stoye, J., Journal of Computer and System Sciences, Vol. 69, 2004, pp. 525-546.[KK99] Finding Maximal Repetitions in a Word in Linear Time, Kolpakov, R. and Kucherov, G., IEEE 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 596-604.[KMP77] Fast Pattern Matching in Strings, Knuth, D. E., Morris, J. H. and Pratt, V. R., SIAM Journal on Computing, Vol. 6, 1977, pp. 323-350.[M75] A New linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String, Manacher, G., Journal of the Association for Computing Machinery, 1975.[M2000] Understanding the Human Genome, Moore, S. K., IEEE Spectrum, Vol. 37, 2000, pp. 33-35.[ML84] An O(nlogn) Algorithm for Finding All Repetitions in a String, Main, M. and Lorentz, R., Journal of Algorithms, Vol. 5, 1984, pp. 422-432.[PB2002] Finding Approximate Palindromes in Strings, Porto, A. and Barbosa, V., Pattern Recognition, 2002.[SG2002] Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree, Stoye, J. and Gusfield, D., Theoretical Computer Science, Vol. 270, 2002, pp. 843-856.[SS99] Periodicity Transforms, Sethares, W. A. and Staley, T. W., IEEE Transactions on Signal Processing, Vol. 47, 1999, pp. 2953-2964.[WYKG2004] Finding Approximate Tandem Repeats in Genomic Sequences, Wexler, Y., Yakhini, Z., Kashi, Y. and Geiger, D., Proceedings of the eighth annual international conference on Computational molecular biology, 2004, pp. 223-232.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 鄭麗月（民88）。從特殊兒童的融合教育談學校行政的配合。特教新知通訊，6(1)，1-4。 2 蔡明富(民87)。融合教育及其對班級經營的啟示。特殊教育與復健學報，6，349-380。 3 游淑惠(民91)。國小校長魅力領導與教師組織承諾及工作滿意度之研究。屏東師範學院國民教育研究所碩士論文，未出版。

 1 常數空間的字串比對演算法之比較分析 2 產生一個擁有特別屬性的字串 3 結合802.11Wi-Fi與802.16Wi-Max於媒體存取控制層之研究 4 在802.16（Wi-Max）系統下正交分頻多重存取之研究 5 以矽化鈦和矽化鎳為閘極電極材料之金氧半電容可靠度之比較 6 以傳導式原子力顯微鏡研究輻射照射過的極薄氧化層在奈米應力作用下之行為 7 在奈米尺度應力下觀察高介電係數介電質氮氧化鉿之退化特性 8 最長迴文子序列和最長重覆子序列 9 成對DNA序列重組問題 10 具限制性之最長共同子序列問題 11 以DNA序列為基礎的加密方法 12 小蘗鹼對胰島素調控之血管平滑肌細胞生長及爬行效應之影響 13 混合HRP+GOD酵素催化層之金氧半結構乾式陣列型血醣感測器 14 探討降雨與淺層崩塌關係之大型試驗 15 幼稚園親師合作的探究歷程

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室