KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//
//  kmp.c
//  
//
//  Created by LiveMac on 2017/8/8.
//
//
#include <stdio.h>
#include <string.h>
void get_next(char* T, int* next)
{
  int i = 1;
  int j = 0;
  next[1] = 0;
  while (i < 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(char* S, char* T, int pos)
{
  int i = pos;
  int j = 1;
  int next[255];
  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()
{
  char S[255] = " aasssbbsdfdsfas";
  S[0] = strlen(S) - 1;
  char T[255] = " sssb";
  char Input[255];
  int pos = 1;
  printf("check[%s][%d], please input substr:\n", S, S[0]);
  while(1)
  {
    scanf("%s",Input);
    int i = 0;
    while(Input[i] != '\0')
    {
      T[i+1] = Input[i];
      i++;
    }
    T[i+1] = '\0';
    T[0] = strlen(T) - 1;
    printf("Input[%s][%lu] -> T[%s][%lu][%d]\n", Input, strlen(Input), T, strlen(T), T[0]);
    int ret = index_kmp(S, T, pos);
    if (ret)
    {
      printf("[%s] has substr [%s] in pos [%d]\n\n", S, T, ret);
    }
    else
    {
      printf("[%s] no substr [%s]\n\n", S, T);
    }
  }
}