找出所有迴文子序列與最長共同迴文子序列

Finding all Palindrome Subsequences and Longest Common Palindrome Subsequences

莊國榮(Kuo-Rong Chuang)

指導教授 ： 李家同

國立暨南國際大學/科技學院/資訊工程學系/碩士(2006年)

https://doi.org/10.6837/NCNU.2006.00029

摘要

迴文是一個字串 S = s1s2...sn = S' = snsn-1...s1。給定一個字串S，假設一個序列P為S的一個子序列且P亦是迴文，則P為S的迴文子序列。
在此篇論文中，我們定義兩個有關於迴文子序列的問題且提出兩個演算法來解決這兩個問題。第一個問題是在給定的一個字串中找出所有迴文子序列。我們的第二個問題是最長共同廻文子序列，其問題定義如下：給定兩條字串X跟Y，最長共同迴文子序列問題是找出一條迴文子序列Z使得Z為X與Y的共同迴文子序列且Z的長度是最長的。針對找出所有迴文子序列問題，我們提出利用迴文子序列特性的演算法來解決這個問題。針對最長共同迴文子序列問題，我們提出一個動態規劃演算法來解決這個問題。

關鍵字

迴文子序列 ； 最長共同迴文子序列

並列摘要

A palindrome is a string S = s1s2...sn = S' = snsn-1...s1. Given a string S, if a sequence P is a subsequence of S and P is also a palindrome, P is a palindrome subsequence of S.
In this thesis, we define two problems about palindrome subsequences and propose two algorithms to solve them. The first problem is finding all palindrome subsequences problem which is to find all palindrome subsequences of a given string. Our second problem is the longest common palindrome subsequence problem which is defined as follow: Given two strings X and Y, the longest common palindrome subsequence problem is to find a palindrome subsequence Z such that Z is a common palindrome subsequence of X and Y and the length of Z is longest. For finding all palindrome subsequences problem, we propose a dynamic programming algorithm by using the property of palindrome subsequences to solve it. For the longest common palindrome subsequence problem, we use a dynamic programming approach algorithm to solve it.

並列關鍵字

Palindrome Subsequence ； Longest Common Palindrome Subsequence

參考文獻

[A2004] Finding Approximate Palindromes in Strings Quickly and Simply, Allison, L., 2004

[C2005] DNA palindromes found in cancer, Choi, Charles Q. , The Scientist, 2005.

[G97] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Gusfied, D., Cambridge University Press, New York, 1997.

[M75] A new Linear-Time “On-Line” Algorithm for Finding the Smallest Initial Palindrome of a String, Manacher, D., J. Assoc. Comput., 1975.

[PB2002] Finding Approximate Palindromes in Strings, Proto, A. H. L. and Barbosa V. C., Pattern Recognition, 2002.