1. KMP概述
改进的匹配算法，又称为KMP算法。当匹配过程中发现主串和模式串字符不等，主串的字符位置指针不再回退，而是利用之前匹配的信息将模式串的匹配位置尽可能的移动，再继续比较的算法。
KMP算法还是相当复杂的，说实话我看了好几个小时才稍微理解了，此处附上一篇我感觉讲的比较到位的博客：详解KMP算法。
2. 代码实现
虽然算法比较复杂，但是实现起来代码量很小，佩服！
/* * 主题：KMP模式匹配算法 * 作者：熊猫大大 * 时间：2020-09-22 */ #include <stdio.h> // 获取子串的next数组 void getNext(char *pattern,int next[]) { //初始化变量 int i, j, len; len = strlen(pattern); i = 0; j = -1; next[0] = -1;//固定值 // 循环设置next数组每个位置的值 while (i < len) { if (j == -1 || pattern[i] == pattern[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } // kmp模式匹配 -1表示匹配失败，其他值表示匹配位置 int kmpIndex(char *main,char* pattern,int next[]) { // 初始化变量 int i, j, mainLen, patternLen; i = 0; j = -1; mainLen = strlen(main); patternLen = strlen(pattern); // 查找匹配串的位置 while (i < mainLen&&j < patternLen) { // 通过next快速调整j的位置 if (j == -1 || main[i] == pattern[j]) { i++; j++; } else { j = next[j]; } } if (j >= patternLen) //匹配成功 { return i - patternLen; } else //失败 { return -1; } } int main() { char * pattern = "bcd"; int* next= (int*)malloc(sizeof(int)*strlen(pattern)); getNext(pattern,next); char * main = "abcd"; printf("位置：%d", kmpIndex(main, pattern, next)); }
