国产一区二区,久久久xxx,久久综合给合久久狠狠色

字符串常見算法之一：查找一個短串在一個長串中位置

介紹的一些字符串處理的問題在日常編程中比較常見，但是在大學讀書的時候幾乎一個都沒有涉及，最近學習了一下在這里介紹給大家，僅供參考。

這些算法與內容包括：

1、    查找一個短串在一個長串中位置；
2、    查找一個字符串中最長的重復子串；
3、    查找一個字符串中重復最多的子串；
4、    兩個字符串最長的公共子串（連續）；
5、    兩個字符串最長的公共子序列（不連續）；
6、    介紹一種強大的數據結構，Suffix tree.

這里有一個PPT：
http://www.shnenglu.com/Files/humanchao/StringAlg.zip

-------------------------------------------------

查找一個短串在一個長串中位置

這個問題傳統的解法時間復雜度為O(m*n)，m、n為兩個串的長度。有一個Sunday算法，可以最大限度的優化這個比較過程，原理如下：

1、建立一個hash table，依次把search各個字符值作為table索引，為table相應的位置一個值（表示字符存在），如果出現重復，后面的位置會覆蓋前面的位置。
例：我們要在"WHICH-FINALLY-HALTS.—AT-THAT-POINT"（簡稱string）查找" AT-THAT "（簡稱pat），剛開始時，把pat與string對齊，查看串string中與串pat 相對應的字符（F），在pat的位置，這個查找的過程時間復雜度通過hash table的下標索引為 O(1)：

2、如果發現沒有，說明字符F之前已經無法與pat匹配，直接跳到position(F)+stringlength(pat)

3、發現”-”在pat位置3，于是重新定位對齊兩串為：

4、倒序（從最后一個向前）比較兩串，發現無法匹配，繼續跳轉->查找->定位
因為上面已經有一個T匹配成功，這次要從HALTS的S來查找，于是定位為：

5、上圖無法匹配，從”--AT-“中A后的”-”繼續查找，重復上過程，最終匹配如圖：

這個算法關鍵點：
1、建立為pat建立hash表，以提高查找字符的速度；
2、對齊跳轉，快速的后移比較，使比較次數減少。

具體的代碼實現可以參考鏈接：

http://blog.csdn.net/unicode1985/archive/2007/05/30/1631038.aspx

posted on 2009-11-25 17:20 胡滿超閱讀(3141) 評論(0) 編輯收藏引用

留言簿(16)

隨筆分類(56)

隨筆檔案(89)

文章分類

推薦博客

搜索

最新隨筆

最新評論

閱讀排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理