天堂久久天堂AV色综合,亚洲国产精品综合久久一线,久久久久女人精品毛片

字符串常見(jiàn)算法之一：查找一個(gè)短串在一個(gè)長(zhǎng)串中位置

介紹的一些字符串處理的問(wèn)題在日常編程中比較常見(jiàn)，但是在大學(xué)讀書(shū)的時(shí)候幾乎一個(gè)都沒(méi)有涉及，最近學(xué)習(xí)了一下在這里介紹給大家，僅供參考。

這些算法與內(nèi)容包括：

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

這里有一個(gè)PPT：
http://m.shnenglu.com/Files/humanchao/StringAlg.zip

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

查找一個(gè)短串在一個(gè)長(zhǎng)串中位置

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

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

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

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

4、倒序（從最后一個(gè)向前）比較兩串，發(fā)現(xiàn)無(wú)法匹配，繼續(xù)跳轉(zhuǎn)->查找->定位
因?yàn)樯厦嬉呀?jīng)有一個(gè)T匹配成功，這次要從HALTS的S來(lái)查找，于是定位為：

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

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

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

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

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

留言簿(16)

隨筆分類(lèi)(56)

隨筆檔案(89)

文章分類(lèi)

推薦博客

搜索

最新隨筆

最新評(píng)論

閱讀排行榜

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



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