## KMP 字串比對演算法

### 一、Failure Function

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