### 實現 KMP 算法,找出所有符合的偏移值。
### 思路:這已經不是某個題目了,這個算法會就是會,不會就不會,本人能力有限,無法完全講清楚這個算法,請參考《算法導論》第三版第 32 章,這章內容會讓你對字符串匹配算法有個清楚的了解,但也只是挑了一些算法講,更多內容見[鏈接](http://www-igm.univ-mlv.fr/~lecroq/string/)。
下面是按照《算法導論》實現的代碼
```
void computePrefixFunction(const string &pattern, vector<int> &pai)
{
int m = pattern.length();
pai.clear();
pai[0] = -1;
int k = -1;
for (int q = 1; q < m; ++q) {
while (k > -1 && pattern[k + 1] != pattern[q])
k = pai[k];
if (pattern[k + 1] == pattern[q])
k = k + 1;
pai[q] = k;
}
}
void KMPMatcher(const string &text, const string &pattern)
{
int n = text.length(), m = pattern.length();
vector<int> pai(m);
computePrefixFunction(pattern, pai);
int q = -1;
for (int i = 0; i < n; ++i) {
while (q > -1 && pattern[q + 1] != text[i])
q = pai[q];
if (pattern[q + 1] == text[i])
q = q + 1;
if (q == m - 1) {
cout << "Pattern occurs with shift" << (i - m + 1) << endl;
q = pai[q];
}
}
}
```