Knuth Morris Pratt(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 End
kmpAlgorithm(文本,模式)
输入:将搜索的主要文本和样式
输出- 找到样式的位置
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