運用雜湊結構解決完整字串比對問題

An Exact String Matching Algorithms Using Hashing Scheme

黃蘭雅(Lan-Ya Huang)

指導教授 ： 李家同

國立暨南國際大學/管理學院/資訊管理學系/碩士(2008年)

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

摘要

在這篇論文裡，我們討論如何解決完整字串比對問題。 字串比對問題是要在字串 中，找出所有字串 發生的位置。 一般的字串比對演算法在線性時間及線性空間完成，其中最有名的為Kunth-Morris-Pratt演算法及Boyer-Moore演算法。 而我們將利用雜湊的結構來解決完整字串比對。 我們的演算法很容易實做，並將此演算法工作在常數空間。而且經過實驗，我們的演算法優於暴力法以及kunth-Morris-Pratt演算法。

關鍵字

字串比對 ； 雜湊法 ； 常數空間

並列摘要

In this thesis, we consider how to solve the exact string matching problem. The exact string matching problem is to find all locations of a pattern string P in a text string T. In general, string matching algorithm problem work in linear time and linear space. The two well-known of them are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (BM) algorithm. We will use the hashing scheme to solve the exact string matching problem. Our method is simple to implement, and our algorithm works in constant space. Experimental shows that our algorithm is better than Brute Force algorithm and KMP algorithm.

並列關鍵字

string matching ； hashing ； constant space

參考文獻

[AC91] Optimal canonization of all substrings of a string, Apostolico, A. and Crochemore, M., Information and Computation, Vol. 95, 1991, pp. 76-95.

[AG86] The Boyer-Moore-Galil string searching strategies revisited, Apostolico, A. and Giancarlo, R., SIAM Journal on Computing, Vol. 15, 1986, pp. 98-105.

[BM77] A fast string searching algorithm, Boyer, R.S. and Moore, J.S., Communications of the ACM, Vol. 20, 1977, pp. 762-772.

[C91] Correctness and efficiency of the pattern matching algorithms, Colussi, L., Information and Computation, Vol. 95, No. 2, 1991, pp. 225-251.

[C94] Fastest pattern matching in strings, Colussi, L., Journal of Algorithms, Vol. 16, No. 2, 1994, pp. 163-189.