不需製表格的字串比對演算法的分析

A Review of String Matching Algorithm without Tables.

羅少文(Shiao Wen Lo)

指導教授 ： 李家同

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

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

摘要

對於字串比對問題，一般的字串比對演算法工作在線性時間及線性空間完成。在那些演算法當中，兩個有名的演算法是Knuth-Morris-Pratt演算法及Boyer-Moore演算法。然而，近幾年發表的演算法可以工作在線性時間及僅需要少的額外的記憶體空間。若這類的演算法工作在線性時間及常數空間，我們稱那些演算法為常數空間字串比對演算法。

在這篇論文，我們執行一個回顧關於常數空間字串比對演算法。我們將介紹五個常數空間字串比對演算法﹕Constant-space matching for a specific pattern, MaxSuffix Matching 演算法, Two Way Matching 演算法, Crochemore-Perrin 演算法和 Galil-Seiferas 演算法。最後，我們也討論他們的結果。

關鍵字

演算法,常數空間

並列摘要

General string matching algorithms for string matching problem work in linear time and linear space. The two well-known famous of them are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (BM) algorithm. However, some string matching algorithms presented in recent years work in linear time and just need a small additional memory space. If such algorithms can work in linear time and simultaneously constant space, we call those algorithms as constant space string matching algorithms.
In this thesis, we perform a review about constant space string matching algorithms.
We will introduce five constant space string matching algorithms: the Constant-space matching for a specific pattern, the MaxSuffix Matching algorithm, the Two Way Matching algorithm, Crochemore-Perrin algorithm and Galil-Seiferas algorithm. Finally, we also discuss the results about them.

並列關鍵字

algorithm ,constant sapce

參考文獻

[A80] Pattern Matching in Strings. In R. V. Book, ed., Aho, A. V., Formal language Theory: Perspectives and Open Problems. Academic Press, Orlando, Fla., 1980, pp. 325-347.

[A87] Generalized String Matching, Abrahamson, K., SIAM Journal on Computing, Vol. 16, 1987, pp. 1039-1051.

[A90] Algorithms for Finding Patterns in Strings, Aho, A. V., Handbook of Theoretical Computer Science, MIT Press/ Elsevier, Vol. A., 1990, pp. 257-300.

[AC75] Efficient String Matching: An aid to bibliographic search, Aho, A. V., Corasick, M. J., Commun. ACM 18, 6(June 1975), pp. 333-340.

[AG86] The Boyer-Moore-Galil Searching strategies revisited, Apostolico, A., Giancarlo, R., SIAM J. Comput. 15, 1(1986), pp. 98-105.