有关KMP的算法具体的实现网上有很多，不具体阐述。这里附上c的实现。

谈谈我自己的理解。KMP相较于朴素算法，其主要目的是为了使主串中的遍历参数i不回溯，而直接改变目标串中的遍历参数j。

比如说要是目标串中没有一个重复的字符，那么当遍历到主串中的i与目标串的j不想等时，只需要把目标串的遍历参数j归1（在这里字符串的首字符用来保存该串的长度），从主串中i的位置从头比对目标串。然后继续向后比较、遍历主串即可。

但是对于大部分的目标串，并不是所有的字符都不同。那么就引入了重复度这个概念。创建next数组，用next数组保存重复度。重复度即为从头开始，第一次出现相同的字符的位置。（如 abaabx 中，第6位的x之前为ab，第一次出现ab且和现在不同的位置是3，那么我就直接回到3继续对比）

遍历到主串，发生不相等时间，目标串中的j自动匹配到next数组中保存的位置，从而主串参数不回溯的目的。

网上还有很多人说strstr比自己写的kmp要快，我觉得大概是strstr其实也用了kmp，但是语句更精简，直接用汇编语言，底层优化之类的（blablabla也是瞎说没有考证）。总之kmp的自动匹配的思维，是非常具有启发意义的。（当然还牵扯到算重复度的思维）。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 1000

typedef char* string;

void get_String(string a){

    string b = (string) malloc (sizeof(char)*N);

    gets(b);

    a[0] = strlen(b),a[1] = '\0';

    strcat( a , b );

}

void get_next(string T,int *next){

    int i = 1,j = 0;

    next[1] = 0;

    while(i<(int)T[0]){

        if(j == 0||T[i] == T[j]){

            ++i,++j;

            if(T[i] != T[j]) next[i] = j;

            else next[i] = next[j];

        }else j = next[j];

    }

}

int index_KMP(string S,string T,int pos){

    int i = pos,j = 1,*next;

    next = (int *)malloc(sizeof(int)*strlen(T));

    get_next(T,next);

    while(i <= S[0]&&j <= T[0]){

        if(j == 0||S[i] == T[j]) i++,j++;

        else j = next[j];

    }

    if(j >T[0]) return i - T[0];

    else return 0;

}

int main(){

    string S,T;

    int ans;

    //初始化字符串S 和 T

    S = (string) malloc (sizeof(char)*N);

    T = (string) malloc (sizeof(char)*N);

    //输入串S 和 T

    //其中S[0]和T[0]分别保存了该串中一共有多少个字符

    get_String(S);

    get_String(T);

    ans = index_KMP(S,T,1);

    if(ans!=0) printf("目标串在母串中出现的位置是  %d   \n",ans);

    else printf("子串不在目标串中出现\n");

    return 0;

}