程序描繪人生
知識(shí)改變命運(yùn)，學(xué)習(xí)成就未來。

隨筆 - 89 文章 - 118 trackbacks - 0

2009年11月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

留言簿(16)

隨筆分類(56)

隨筆檔案(89)

文章分類

推薦博客

在你身邊
胡滿超的非技術(shù)博客

搜索

閱讀排行榜

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

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

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

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

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

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

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

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

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

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

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

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

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

這個(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 胡滿超閱讀(3148) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品