Failure Function & 字串比對

網路上的教學都寫的有夠複雜有夠難懂，只好自己寫一篇。

首先先介紹 Failure Function

它的用途是讓你在比對字串時，知道可以向後跳多少，藉此減少比較次數。
其原理就是利用字串本身有相同的 前綴 跟 後綴 (簡單來說就是有部分一樣的地方)，所以移動了這樣的距離後，因為前綴移動到的地方跟後綴一模一樣，所以不用再重複比較，最後只需要比較後面不一樣的地方即可。

中文的教學有看沒有懂，反而英文在 stackoverflow 有一篇文章把算法寫的相當清楚。
http://stackoverflow.com/questions/16125544/kmp-failure-function-calculation

failure function (by definition, this is the length of the longest prefix of the string which is a suffix also)

這定義很重要，知道了這定義就完全明白這是什麼鬼東西。

這時候就可以實際使用別人寫好的字串比對教學程式來驗證自己的想法

http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html

這網站的教學文雖然寫的不太好，但工具很好，在理解 Failure Function 之後，用這工具就會馬上理解字串如何比對了。