1.首先获得我们的next数组的值。

  1. #include <stdio.h>
  3. typedef struct
  4. {
  5. int Length;             // 长度
  6. char* data;              // 数据
  7. }Com;
  10. void get_next( Com T, int *next )
  11. {
  12.     int j = -1;
  13.     int i = 0;
  14.     next[0] = -1;
  16. //不会有next[T.Length]
  18.     while( i < T.Length - 1 )
  19.     {
  20.         if(-1 == j || T.data[i] == T.data[j] )
  21.         {
  22.             i++;
  23.             j++;
  24.             next[i] = j;
  25.         }
  26.         else
  27.         {
  28.             j = next[j];
  29.         }
  30.     }
  31. }
  32. int main()
  34. {
  35.     Com T;
  36.     T.Length = 9;
  37.     T.data = "ababaaaba";
  38.     int next[255];
  39.     get_next( T, next );
  41.     return 0;
  42. }

image.png

  1. 整体程序 ```c

    include

typedef struct { int Length; // 长度 char* data; // 数据 }Com;

void get_next( Com T, int *next ) { int j = -1; int i = 0; next[0] = -1;

//不会有next[T.Length]

  1. while( i < T.Length - 1 )
  2. {
  3.     if(-1 == j || T.data[i] == T.data[j] )
  4.     {
  5.         i++;
  6.         j++;
  7.         next[i] = j;
  8.     }
  9.     else
  10.     {
  11.         j = next[j];
  12.     }
  13. }

}

// 返回子串T在主串S第pos个字符之后的位置 // 若不存在，则返回0 int Index_KMP( Com S, Com T) { int i = 0; int j = -1; int next[255];

  1. get_next( T , next );
  3. while( i < S.Length && j < T.Length )  //T.Length = 4;
  4. {
  5.     if( -1 == j || S.data[i] == T.data[j] )   //S.data[5] = T.data[0]  61  72   83
  6.     {
  7.         i++;
  8.         j++;
  9.     }
  10.     else
  11.     {
  12.         j = next[j];//如果不相等就回到那个被匹配的位置
  13.     }
  14. }
  16. if( j >= T.Length )
  17. {
  18.     return i - T.Length;
  19. }
  20. else
  21. {
  22.     return -1;
  23. }

}

int main()

{ Com S; Com T;

  1. S.data = "0123456yu815";     //返回7   0123456  （包括0的） 也就是第八个位置
  2. S.Length = strlen(S.data);
  4. T.data = "yu";
  5. T.Length = strlen(T.data);
  7. int a;
  8. a = Index_KMP(S,T);
  9. printf("%d",a);
  11. return 0;

}

  1. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/812258/1620526002431-f86af599-9aef-443e-9eb3-061bd9eb2ec2.png#clientId=u9cc2e6aa-5293-4&from=paste&height=80&id=u5ee6d7e2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=127&originWidth=1220&originalType=binary&size=12151&status=done&style=none&taskId=u651cbc71-1d78-478a-8c80-9d1b8563bbb&width=770)<br />3.还是有一些不太好的地方<br />比如：<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/812258/1620526416049-ea8478b1-6b9c-4e9b-a1b8-7c1bbfb53c41.png#clientId=u0eb6a8fb-9713-4&from=paste&height=140&id=udd9e853c&margin=%5Bobject%20Object%5D&name=image.png&originHeight=279&originWidth=528&originalType=binary&size=85787&status=done&style=none&taskId=u4951988f-26c5-4e8e-bb6a-c0eee5d22ab&width=264)
  2. ```c
  3. //改进next数组运算
  4. void get_next( Com T, int *next )
  5. {
  6.     int j = -1;
  7.     int i = 0;
  8.     next[0] = -1;
  10. //不会有next[T.Length]
  12.     while( i < T.Length - 1 )
  13.     {
  14.         if(-1 == j || T.data[i] == T.data[j] )
  15.         {
  16.             i++;
  17.             j++;
  18.             if(T.data[i] != T.data[j])
  19.             {
  20.                 next[i] = j;
  21.             }
  22.             else
  23.             {
  24.                 next[i] = next[j];
  25.             }
  27.         }
  28.         else
  29.         {
  30.             j = next[j];
  31.         }
  32.     }
  33. }