Gusfield Algorithm

也就是俗稱的Z algorithm

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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