KMP 字串比對演算法

字串比對演算法是鼎鼎大名的 KMP，把暴力法的O(m*n)直接砍成O(m+n)，覺得寫得不夠詳細可以看 references 的資料，很值得揣摩！

一、Failure Function

運用一個Failure Function的概念，簡單來說就是「從字串S中的i位置往前延伸，最多可以往前幾位(< i) 使得往前的這個位數是S的前綴」。舉例來說：

F(6) = 3 因為
abcabca cab
      abca bcacab

F(9) = 1 因為
abcabcacab
               ab cabcacab

[注意] 不同人解釋「足碼」可能不同！

二、Implement strStr()　詳解 ：KMP Algorithm

class Solution {
public:
    vector<int> failure;
    
    void GetFailureFunction(string& needle){
        
        failure.assign(needle.size(), -1);
        
        for(int j = 1; j < needle.size(); j++){
            int i = failure[j-1];
            
            while( (needle[j] != needle[i+1]) && (i>=0) ){
                i = failure[i];
            }
            
            if(needle[j] == needle[i+1]){
                failure[j] = i+1;
            }
        }
    }

    int KMP(string& haystack, string& needle){
        int i = 0, j = 0;
        while( i<haystack.size() && j<needle.size() ){
            if( haystack[i] == needle[j] ){
                i++; j++;
            }
            else{
                if( j == 0 )
                    i++;
                else
                    j = failure[j-1] + 1;
            }
        }
        
        if(j < needle.size())
            return -1;
        else
            return i-needle.size();
    }

    int strStr(string haystack, string needle) {
        
        GetFailureFunction(needle);
        
        return KMP(haystack,needle);
    }
};

[補記] 原來KMP被打爆了，沒有最快只有更快XD
http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap10.htm

References

https://www.ptt.cc/bbs/b99902HW/M.1300796484.A.EE1.html

http://www.cppblog.com/suiaiguo/archive/2009/07/16/90237.html

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://www.uml.org.cn/c++/201207261.asp