臺灣博碩士論文加值系統

給定一字串 ， 被稱為字串 的倒轉。 是ㄧ個非空的字串。字串 被稱為精確迴文，而字串 被稱為間隔迴文。我們這篇論文要解決的問題定義如下：給定一長度為 的字串 ，找尋在字串 中所有的精確迴文及間隔迴文。
　　在這篇論文中，我們提出一個基於字尾樹的演算法來解決這個迴文找尋問題。以下是我們演算法的描述：ㄧ開始，我們反轉給定的字串 ，並稱這新的字串為 。我們為這兩字串 及 建造ㄧ字尾數。我們在這字尾數上標定前收集，後收集和 之後，我們提出兩公式來找尋迴文。使用第一個公式 ，我們將找出精確迴文。近一步地，我們使用第二個公式 來找尋間隔迴文。這兩公式是幫助我們解決這迴文找尋問題的主要技巧。

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 v
List of Tables vi
Chapter 1 Introduction 1-1
1.1 Motivations and Previous Works 1-1
1.2 Thesis Organization 1-2
Chapter 2 Manacher Algorithm 2-1
2.1 The Brute Force Algorithm 2-1
2.2 The Manacher Algorithm 2-3
2.3 A Full Example of Manacher Algorithm 2-7
Chapter 3 Solving the Palindrome Detection Problem Based upon Suffix Trees 3-1
3.1 Term Definitions 3-1
3.2 Finding Exact Palindromes 3-6
3.3 Finding Gaped Palindromes 3-10
3.4 Full Example for Finding All Palindromes 3-17
Chapter 4 Conclusion 4-1
Bibliography 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.