程序描繪人生
知識改變命運，學習成就未來。

隨筆 - 89 文章 - 118 trackbacks - 0

2008年7月

>

日

一

二

三

四

五

六

29

30

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

31

1

2

3

4

5

6

7

8

9

留言簿(16)

隨筆分類(56)

隨筆檔案(89)

文章分類

推薦博客

在你身邊
胡滿超的非技術博客

搜索

閱讀排行榜

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

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

這些算法與內容包括：

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)：