Knuth-Morris-Pratt算法
KnuthMorrisPratt(KMP)是一种算法，它从左到右检查字符。当某个模式的子模式在子模式中出现多个时，它会使用该属性来提高时间复杂度，即使在最坏的情况下也是如此。
KMP的时间复杂度为O(n)。
输入输出
Input: Main String: “AAAABAAAAABBBAAAAB”, The pattern “AAAB” Output: Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14
算法
findPrefix(pattern,m,prefArray)
输入-模式，模式长度和用于存储前缀位置的数组
输出-存储前缀位置的数组
Begin
length := 0
prefArray[0] := 0
for all character index ‘i’ of pattern, do
if pattern[i] = pattern[length], then
increase length by 1
prefArray[i] := length
else
if length ≠ 0 then
length := prefArray[length - 1]
decrease i by 1
else
prefArray[i] := 0
done
EndkmpAlgorithm（文本，模式）
输入：将搜索的主要文本和样式
输出- 找到样式的位置
Begin
n := size of text
m := size of pattern
call findPrefix(pattern, m, prefArray)
while i < n, do
if text[i] = pattern[j], then
increase i and j by 1
if j = m, then
print the location (i-j) as there is the pattern
j := prefArray[j-1]
else if i < n AND pattern[j] ≠ text[i] then
if j ≠ 0 then
j := prefArray[j - 1]
else
increase i by 1
done
End示例
#include<iostream>
using namespace std;
void findPrefix(string pattern, int m, int prefArray[]) {
int length = 0;
prefArray[0] = 0; //first place is always 0 as no prefix
for(int i = 1; i<m; i++) {
if(pattern[i] == pattern[length]) {
length++;
prefArray[i] = length;
}else {
if(length != 0) {
length = prefArray[length - 1];
i--; //decrease i to avoid effect of increasing after iteration
}else
prefArray[i] = 0;
}
}
}
void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) {
int n, m, i = 0, j = 0;
n = mainString.size();
m = pattern.size();
int prefixArray[m]; //prefix array as same size of pattern
findPrefix(pattern, m, prefixArray);
loc = 0;
while(i < n) {
if(mainString[i] == pattern[j]) {
i++; j++;
}
if(j == m) {
locArray[loc] = i-j; //item found at i-j position.
loc++;
j = prefixArray[j-1]; //get the prefix length from array
}else if(i < n && pattern[j] != mainString[i]) {
if(j != 0)
j = prefixArray[j-1];
else
i++;
}
}
}
int main() {
string str = "AAAABAAAAABBBAAAAB";
string patt = "AAAB";
int locationArray[str.size()];
int index;
kmpPattSearch(str, patt, locationArray, index);
for(int i = 0; i<index; i++) {
cout << "Pattern found at location: " <<locationArray[i] << endl;
}
}输出结果
Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14