亚洲午夜精品久久久久久浪潮 ,91精品国产色综久久,久久人人爽人人爽人人爽

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

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

這些算法與內容包括：

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

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

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

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

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

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

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

3、發(fā)現(xiàn)”-”在pat位置3，于是重新定位對齊兩串為：

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

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

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

具體的代碼實現(xiàn)可以參考鏈接：

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

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

留言簿(16)

隨筆分類(56)

隨筆檔案(89)

文章分類

推薦博客

搜索

最新隨筆

最新評論

閱讀排行榜

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



網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理