KMP代码实现

void GeneratePrefix(const string& pattern, int* prefix) { int length = pattern.size(); prefix[1] = 0; int LOLP = 0; //LOLP表示最长的前缀数组 int NOCM; //number of characters matched for(NOCM = 2; NOCM <= length; ++NOCM) { while(LOLP > 0 && pattern[NOCM-1] != pattern[LOLP]) LOLP = prefix[LOLP]; if(pattern[NOCM-1] == pattern[LOLP]) ++LOLP; prefix[NOCM] = LOLP; } } void KMPMatch(const string& pattern, const string& target) { int size1 = pattern.size(); int size2 = target.size(); if(size1 > size2) return; int prefix[size1]; GeneratePrefix(pattern, prefix); int NOCM = 0; for(int i = 0; i < size2; ++i) { while(NOCM > 0 && pattern[NOCM] != target[i]) NOCM = prefix[NOCM]; if(pattern[NOCM] == target[i]) ++NOCM; if(NOCM == size1) { cout << "Matched! The start index is:" << i-size1+1 << endl; NOCM = prefix[NOCM]; } } }