KMP算法

#include <cstdio> #include <vector> #include <string> using namespace std; //前后缀表 void prefix_table(string pattern, vector<int> &prefix, int n) { prefix[0] = 0; int len = 0; int i = 1; while (i < n) { printf("i=%d,len=%d\n", i, len); if (pattern[i] == pattern[len]) { len++; prefix[i] = len; i++; } else { if (len > 0) len = prefix[len - 1]; else { prefix[i] = len; i++; } } } } //后移一位 void move_prefix_table(vector<int> &prefix, int n) { for (int i = n - 1; i > 0; i--) { prefix[i] = prefix[i - 1]; } prefix[0] = -1; } void kmp_search(string text, string pattern) { int n = pattern.size(); vector<int> prefix(n, 0); prefix_table(pattern, prefix, n); move_prefix_table(prefix, n); //text[i] len(text) = m //pattern[j] len(pattern) = n int i = 0, j = 0, m = text.size(); while (i < m) { if(j == n - 1&& text[i]==pattern[j]){ printf("Found pattern at %d\n",i-j); j = prefix[j]; //找到相同的之后继续向后走 } if (text[i] == pattern[j]) { i++, j++; } else { j = prefix[j]; if(j==-1){ i++,j++; } } } } int main() { string pattern = "ababcabaa"; string text = "abababcabaababab"; kmp_search(text,pattern); /* vector<int> prefix(9, 0); int n = 9; prefix_table(pattern, prefix, n); move_prefix_table(prefix, n); int i; for (i = 0; i < n; i++) { printf("%d\n", prefix[i]); } */ return 0; }