2012年7月20日 星期五

Gusfield Algorithm

也就是俗稱的Z algorithm

概念也很簡單,就是記錄每個後綴與母字串的最長共同前綴

他的時間複雜度跟KMP是一樣的,都是O(n)

但我覺得他的概念比較簡單,實作方便

他的精隨在於:記錄比對到的最右界R,及比對到此右界的後綴起點L

並且可以分成三種情況討論:

1. 要比的後綴根本沒被比過 -> 就去比吧

2. 要比的後綴的前面部分已比過但長度未知 -> 繼續比吧

3. 要比的後綴的前面部分已比過且長度已知 -> 直接記錄吧

我的code: http://codepad.org/OPoY0Pu4

若要做字串匹配,直接把兩個字串黏在一起(要找的放在前面)
看哪些點的Z[]值 = 找尋字串的長度,便可知其出現的數量


有人會問這樣他的功能不是跟KMP一樣嘛?學他做什麼?

我覺得應該是為了增加另外一種想法吧!因為經過轉換後,就可以用在KMP所無法運用的地方了

所以在這邊稍稍分析一下兩者的差別:

KMP: 每個前綴與其後綴的次長共同前綴(最長的後綴)
Z_Vl: 每個後綴與母字串的最長共同前綴(單純的長度)

大致記得他們的差異,就可以在碰到題目時,適當的做運用。

2 則留言:

  1. 應該是
    從 strlen (T) 開始
    看哪些點的Z[]值 ">=" 找尋字串的長度,便可知其出現的數量
    這樣才對(?

    回覆刪除