kmp算法

kmp算法运用于字符串匹配，具体实现过程如下：

拿从母串中找是否存在某个字串举例

1.求字串的next数组，什么是next数组，即每个字母所在位置对应的最长相等前后缀，例如abcabf的next数组就是000120，那如何找一个next数组呢

void getnext(int next[], char* s) { int len_ = strlen(s);//求出字符串长度 int j = 0; next[0] = 0; for (int i = 1; i < len_; i++) { while (j > 0 && s[j] != s[i]) { j = next[j - 1];//回退 } if (s[j] == s[i]) { j++; } next[i] = j; } }

首先，我们将next首元素赋值为0，j是前缀指针，i是后缀指针，i一直向后移动，只有当i和j指向元素是相同的时候，j才向后移动。一旦不相等，j就一直回退，一种可能是到相等位置，一种可能一直找不到相等的，回到首元素位置。要注意的是，j不仅是前缀指针，它同时也是每个元素对应的next

2.将子串和母串进行比对

i指向母串，一直向后移动，j指向子串，从遇到相等的开始，j也开始移动。一旦不相等，j就开始回退，也是两种情况一种可能是到相等位置，一种可能一直找不到相等的，回到首元素位置。一旦j移动到元素末尾，即表示存在

bool judge(char* a, char* b,int next[]) { int j = 0;//这是字串 int i = 0;//这是母串 int len1 = strlen(a); int len2 = strlen(b); for (i = 0; i < len2; i++) { while (j > 0 && a[j] != b[i]) { j = next[j - 1];//回退 } if (a[j] == b[i]) { j++; } if (j == len1) { return true; } } if (j != len1) { return false; } return 0; }

这是全部实现过程，如有错误，请指出

void getnext(int next[], char* s) { int len_ = strlen(s);//求出字符串长度 int j = 0; next[0] = 0; for (int i = 1; i < len_; i++) { while (j > 0 && s[j] != s[i]) { j = next[j - 1];//回退 } if (s[j] == s[i]) { j++; } next[i] = j; } } bool judge(char* a, char* b,int next[]) { int j = 0;//这是字串 int i = 0;//这是母串 int len1 = strlen(a); int len2 = strlen(b); for (i = 0; i < len2; i++) { while (j > 0 && a[j] != b[i]) { j = next[j - 1];//回退 } if (a[j] == b[i]) { j++; } if (j == len1) { return true; } } if (j != len1) { return false; } return 0; } int main() { char str1[100];//子串 char str2[200];//母串 int next[101]; scanf("%s%s", str1, str2); getnext(next, str1); bool res = judge(str1, str2,next); printf("%s", res ? "true" : "false"); return 0; }