KMP算法
给定一个 s 字符串和一个 h 字符串，在 s 字符串中找出 h字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
事例：
输入：s = "aabaabaaf" h = "aabaaf"
输出：3
在该算法中主要难在next数组的建立，该数组有多种建立方法，我讲的是我认为较简单的.
每一个字符串数组都有一个自己的next数组，例如：
h = "aabaaf"
next[6] = { 0, 1, 2, 0, 0, 5 }
下面我们来研究如何建立next数组：
为了方便我们建立一个新的字符串和h一样
s = "aabaaf"
next数组表示的是什么意思呢？
next[0] = 0 表示 s[0]与h[5]对齐时，s[i]前面与h相等的字母个数 且个数等于下标否则为0;(以此推广）
next[0] = 0;
next[1] = 1;
next[2] = 2;
next[3] = 0;
next[4] = 0;
next[5] = 5;
由此我们就建立了next数组，代码如下：
void git_next(char *h, int *next,int m)
{
b[0] = 0;
for(int i = 1; i < m; i++)
{
int n = 0;
for(int j = 1;j<=i;j++)
{
if(h[i-j] == h[m-1-j])
{
n++;
}
}
if(n == i)
{
next[i] = n;
}
else
{
next[i] = 0;
}
}
}
那么next数组有什么用呢？
在开始的时候我们提出了一个题：
给定一个 s 字符串和一个 h 字符串，在 s 字符串中找出 h字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
事例：
输入：s = "aabaabaaf" h = "aabaaf"
输出：3
当我们比较到
0 1 2 3 4 5 6 7 8 9 10 11 //下标
a a b a a b a a b a a f
a a b a a f
0 1 2 3 4 5 //下标
这个时候通常是一个一个移动s字符串，直到下面位置（中间有好几步），但KMP会直接移动到该位置，并且直接从s[5]和h[2]比较，省略很多步。
0 1 2 3 4 5 6 7 8 9 10 11 //下标
a a b a a b a a b a a f
a a b a a f
0 1 2 3 4 5 //下标
那么KMP是如何做到的呢？
我们可以把next数组标在下方
0 1 2 3 4 5 6 7 8 9 10 11 //下标
a a b a a b a a b a a f
a a b a a f
0 1 2 3 4 5 //下标
0 1 2 0 0 5 //next数组
移动后
a a b a a b a a b a a f
a a b a a f
0 1 2 0 0 5 //next
所以当h[5]与s[5]不同时，h字符串会在next[5]之前找到值最大的next[2]并把h[2]与s[5]对齐比较;（在next[5]之前next[2]最大）
推广：
当h[x]与s[i]不同时，h字符串会在next[x]之前找到值最大的next[y]并把h[y]与s[i]对齐比较;
下面我们看看代码：
#include <stdio.h>
#include <string.h>
void git_next(char *a, int *b,int m)
{
b[0] = 0;
for(int i = 1; i < m; i++)
{
int h = 0;
for(int j = 1;j<=i;j++)
{
if(a[i-j] == a[m-1-j])
{
h++;
}
}
if(h == i)
{
b[i] = h;
}
else
{
b[i] = 0;
}
}
}
int KMP(char s[],char h[],int b[],int s_len,int h_len)
{
int i,j;
for(i = 0, j = 0; i < s_len&& j <h_len; i++,j++)
{
if(s[i] != h[j])
{
int max = 0;
for(int k = 0;k<j;k++)
{
if(b[max]<b[k])
{
max = k;
}
}
j = max;
}
}
return i-h_len;
}