(3.230.173.249) 您好！臺灣時間：2021/04/21 02:54

### 詳目顯示:::

:

• 被引用:0
• 點閱:146
• 評分:
• 下載: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 基於字尾樹演算法之避免交互雜交DNA微陣列探針集合自動化選擇研究 4 使用字尾樹發展引子挑選演算法 5 創造性問題解決融入科學遊戲教學對國小高年級學生創造力及學習成就之影響 6 棕櫚酸甲酯是一個視網膜與血管周邊脂肪組織所釋放之強效血管放鬆因子 7 以蛋白質體學方法分析及鑑定眼房液內的蛋白質於糖尿病視網膜病變中所扮演之病理生理角色 8 手術所致腦創傷後植入多孔可吸收之膠原蛋白糖胺聚糖基質對功能改善，神經再生與血管新生之研究 9 探討高表現量乙醛去氫酶卵巢上皮癌之幹細胞特性之研究 10 探討腫瘤壞死因子α在嗎啡耐藥性所扮演的角色：腫瘤壞死因子α抑制劑Etanercept的作用 11 探討白藜蘆醇與小分子藥物在豬軟骨細胞中軟骨保護作用與分子機制 12 針織機械業導入知識管理系統關鍵因素與企業競爭力之關聯性研究 13 探討正向情緒對於疼痛感知及疼痛相關情緒之調控作用：腦磁波研究

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