一、next数组(简单易懂)
next函数值仅取决于模式串本身，与主串无关
next数组的生成这里有两种方式：
1.前缀后缀匹配
2.字符串下标匹配
以一个数组为例：
a b a b a a a b a b a a 
我们要生成这个模式串的next数组，那么首先第一件事就是为这些字符标号，
如下；

  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a

方法一 	前缀后缀匹配

前缀和后缀进行比较，如果前缀和后缀没有相同前缀，则为0+1，如果相同，则相同的字符个数+1；
前缀取s[n]之前字符的n-2位，后缀取s[n]之前n-1字符后面的后n-2位。

  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1
 1.next[1],next[2]无论是什么模式串数组，永远都是0和1。
 
 2.next[3]：如上，序号j[3]对应的模式串s[3]，那么我们就看模式串s[3]前面的
 字符即可，即为a b,那么s[3]的前缀为a,后缀为b,a和b不相同,则next[3]为0+1=1;
 
 3.next[4]:序号j[4]对应的s[4],找s[4]的前面字符，为a b a,字符前缀为a、ab；
 后缀为ba, a;有1个相同字符，则next[4]=1+1=2;

 4.next[5]:序号j[5]对应的s[5],找s[5]的前面字符，为a b a b,字符前缀为a、ab
 aba三个，后缀为bab、ab、b三个，进行比较，有字符串ab相同，则next[5]=2+1=3

 以此类推......

 5.next[12]:序号j[12]对应的模式串字符为s[12],取前n-1个字符，为a b a b a a a b a b a,前缀为：ababaaabab,后缀为babaaababa.
 可看出前缀中 ababa与后缀中ababa5个字符相同，则next[12]=5+1=6;

最终生成的next字符串为：
    j: 1 2 3 4 5 6 7 8 9 10 11 12
    s: a b a b a a a b a b  a  a
 next: 0 1 1 2 3 4 2 2 3 4  5  6

方法二  字符串下标匹配
  序号j: 1 2 3 4 5 6 7 8 9 10 11 12
模式串s: a b a b a a a b a b  a  a
 next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 1.next[1],next[2]无论是什么模式串数组，永远都是0和1。
 
 2.next[3]：我们要生成next[3]的值，就要先看前一位s[2]对应的next值为1,那么
 以对应的next值1为下标，s[1]与s[2]比对，不相同，则next[3]为0+1=1。
 
 3.next[4]:要生成next[4],首先要看前一位s[3]对应的next值为1，则以对应的
 next值为下标，s[3]不变,s[1]为a,s[3]也为a,相同，则以s[3]下标1进行加一，为
 1+1=2,所以，next[3]=2;
 
 4.next[5]，next[6]:同理。next[5]=3,next[6]=4
 
 5.next[7]:到这就有问题了，前一位s[6]所对应的next下标为4，所以，s[6]和s[4]对比，不相同！那么，继续看s[4]所对应的next下标，
 为2，s[6]不动，永远作为对比方，与s[4]对应next下标数字为序号再次进行对比，以此类推，s[2]=b,
 s[6]=a,不相同！继续操作，s[2]的next值为1，以是s[1]为下标，继续对比，s[1]=s[6]=a.到此为止,next[7]的值为s[2]的next值+1，为2.
 
 6.后面同理。
 

二、nextval（有手就行）
这里我们只介绍最简单的生成nextval数组的方法，nextval数组第一个字符永远为0。

既然我们上面生成了next数组，nextval数组直接通过next数组便可生成。

若不同，填入next的值；若相同，填入该值对应的序号的nextval.
   序号 : 1 2 3 4 5 6 7 8 9 10 11 12
 模式串s: a b a b a a a b a b  a  a
  next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 nextval: 0 
 
 1.nextval[1]=0,默认值
 2.nextval[2]：s[2]对应的next值为1，则以1为下标s[1],与s[2]进行对比,不相同，
 则将s[2]对应的next值直接下发到nextval，nextval[2]=next[2]=1;
 3.nextval[3]：s[3]对应的next值为1，则以1为下标，与s[3]进行对比，相同，则nextval[3]=nextval[1]=0;
 4.nextval[4]：s[4]对应的next值为2,则以2为下标,与s[4]进行对比，相同，则nextval[4]=nextval[1]=0;
 5.依次同理.....
 6.nextval[12]:s[12]对应的next值为6，则s[6]与s[12]对比,相同，则nextval[12]=nextal[6]=4;
 
 最终生成的nextval为：
   序号 : 1 2 3 4 5 6 7 8 9 10 11 12
 模式串s: a b a b a a a b a b  a  a
  next[]: 0 1 1 2 3 4 2 2 3 4  5  6
 nextval: 0 1 0 1 0 4 2 1 0 1  0  4

刚刚开始遇到这个问题说实话完全懵逼，然后简单搜了下，还是理解的模棱两可。最后看了几篇博客，现在才算是真正的理解了。
首先在将例子之前先说说这个next数组求解的思路：
第一位的next的值是0，第二位的next的值为1，后面求解每一位的next的值时。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，如果不等，向前继续寻找next值对应的内容与前一位进行比较（向前继续寻找next值对应的内容与next值对应的内容的next前一位进行比较），直到找到某个位上的内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。
求串′ababaaababaa′的next数组
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
1、前两位：next数组前两位规定是0，1 即前两位ab对应的next数组为01，则：
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
 
 
 
 
 
 
 
 
 
 
2、接下来看第三位，按照next数组求解方法。第三位a的前一位为第二位的b，b的next值为1对应内容为a，b与a不同，向前继续寻找next值对应的内容来与前一位进行比较。因为找到第一位都没有找到与前一位相等的内容，所以第三位a的next值为1，则：
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
 
 
 
 
 
 
 
 
 
3、接下来看第四位b，b的前一位a的next值1对应内容为a，相同，所以该位b的next值就是前一位a的next值加上1，即为2
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
 
 
 
 
 
 
 
 
4、接下来看第五位a，a的前一位b的next值2对应内容为b，相等，所以该位a的next值就是前一位b的next值加上1，即为3
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
 
 
 
 
 
 
 
5、接下来看第六位a，a的前一位a的next值3对应内容为a，相等，所以该位a的next值就是前一位a的next值加上1，即为4
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
 
 
 
 
 
 
6、接下来看第七位a，a的前一位a的next值4对应内容为b，不相等，向前继续寻找next值对应的内容来与前一位进行比较，b的next值2对应的内容为b，依旧不相等，继续向前寻找，第二位b的next值1对应内容为a，相等。因为是在第二位b处实现的相等，所以第七位a的next值为第二位b的next值上加1，即为2
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
 
 
 
 
 
7、接下来看第八位，同样道理，得出b的next值为2
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
2
 
 
 
 
8、接下来看第九位，前一位b的next值2对应内容为b，相等，所以此处next值为3
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
2
3
 
 
 
9、第十位同理可得，为4
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
2
3
4
 
 
10、第十一位a的前一位b的next值4对应内容为b，相等，所以此处next值为5
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
2
3
4
5
 
11、最后，第十二位同理可以得到next值位6
模式串
a
b
a
b
a
a
a
b
a
b
a
a
下标
1
2
3
4
5
6
7
8
9
10
11
12
next数组
0
1
1
2
3
4
2
2
3
4
5
6

题目描述

字符串的子串定位称为模式匹配，模式匹配可以有多种方法。简单的算法可以使用两重嵌套循环，时间复杂度为母串与子串长度的乘积。而KMP算法相对来说在时间复杂度上要好得多，为母串与子串长度的和。但其算符比较难以理解。

在KMP算法中，使用到了一个next数组。这个数组就是在比较失配时母串指针不必回溯，而子串指针移动相应位置即可。请参考教材next数组的计算公式与算法，编程实现之。

输入

一个模式串，仅由英文小写字母组成。长度不大于100。

输出

输出模式串对应的移动数组next。每个整数后跟一个空格。

样例输入 Copy

abaabcac

样例输出	Copy

0 1 1 2 2 3 1 2
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char a[105];
char b[105];
int next[105];
int L1, L2;

void f()
 {
    int i=0,j=-1;
    next[0]=-1;
    while(i<strlen(a)){
        if(j==-1||a[i]==a[j]){
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
     }
 }


int main()
{
    int i;
    scanf("%s", a);
    f();
    for(i=0;i<strlen(a);i++)
        printf("%d ",next[i]+1);
       
    return 0;
}

一. 理解字符串的next数组值

next数组值的概念涉及到字符串匹配的问题，比较抽象，先介绍一些预备知识：

1. 主串和模式串

       例如我们想知道一个字符串是否包含另一个字符串时，如串S="bbc abcdab abcdabcdabde"中是否包含串s="abcdab"，那么S称为主串，s称为模式串。解决这个字符串匹配问题的算法就是KMP算法。KMP算法与next数组关系密切。有关KMP算法：KMP算法链接。

1.1 字符串的前缀和后缀

给定字符串"bread",

         前缀：是指除最后一个字符外，剩余字符的全部头部组合。"b,br,bre,brea",共有四个元素。

         后缀：是指除第一个字符外，剩余字符的全部尾部组合。"read,ead,ad,d"，共有四个元素。

1.2 字符串的前缀和后缀的最大长度

  含义：前缀和后缀相同元素的最大长度。举例说明如下：

以变量S表示ABCDAB,下面是S的各个子串

 A：前缀和后缀都是空集，没有相同元素，长度为0

 AB：前缀[A],后缀是[B],没有相同元素，长度为0

 ABC:前缀是[A, AB],后缀是[BC, B]，长度为0

ABCD:前缀是[A, AB, ABC],后缀是[BCD, CD, D]，没有相同元素，长度为0

ABCDA:前缀是[A, AB, ABC,ABCD],后缀是[BCDA, CDA, DA, A]，共同元素是[A],长度为1

ABCDAB:前缀是[A, AB, ABC,ABCD, ABCDA],后缀是[BCDAB, CDAB, DAB, AB, B]，共同元素是[AB],长度为2

因此，字符串变量S前缀和后缀的最大长度=2

2. next[j]=k数组

       利用KMP算法将模式串从第一个位置开始自坐向右移动逐个匹配主串时，当模式串第j个字符与主串第i个字符失配，为了提高匹配效率，避免回溯，将模式串在失配位置向右移动j-next[j]位，再继续匹配，j叫做已匹配值（0<=j<len(s)）。

       next[j] = k的含义是模式串在第j个字符失配时（对应着主串第i个字符），将模式串中第k个字符与主串的第i个字符对齐之后，再进行匹配。注意以下几点：

这里所说字符串的第j个字符是指的第j+1个位置，即默认第0个字符对应第1位，j最大值比模式串长度要小1；
	
next[j]的值仅对模式串而言，它等于前j位（第0到第j-1个字符）组成的子符串所对应前缀和后缀的最大长度
	
next数组有默认是next[0]=-1开头，也有next[0]=0开头，后者只需要将以-1开头的next每个元素加1即可；
以下是以next=-1开头讨论，举例说明



        如上图所示，此时在第j位字符D出现失配，j=6，已匹配值m=6，找对应前6位的模式子串（第0到第5个字符）,取每一个子串前缀后缀的最大长度作为整个子串的最大长度，结果为2；所以，第j位D对应的next[j]=2，模式串向右移动6-2=4位，或者说是将第next[j]个字符（对应字符C）与失配位置对齐后，然后再进行匹配，如下图所示：



3. 最大长度与next数组的关系

next 数组
	
pattern
			
A
			
B
			
C
			
D
			
A
			
B
			
D
		
j
			
0
			
1
			
2
			
3
			
4
			
5
			
6
		
最大长度
			
0
			
0
			
0
			
0
			
1
			
2
			
0
		
next[j](-1开头)
			
-1
			
0
			
0
			
0
			
0
			
1
			
2
		
next[j](0开头)
			
0
			
1
			
1
			
1
			
1
			
2
			
3
		
二. 手动求模式串的next数组

1. s="aaab" 对应的next值为{-1,0,1,2}或者分别加1为{0,1,2,3}，解释如下：

第一位默认为0，next[0]=-1

第二位，前面的子串只有a，前缀和后缀为空集，最大长度=0，nex[1]=0

第三位，子串[a,aa],a的子串长度为0，aa的前缀和后缀共有的元素"a",长度=1，next[2]=1

第四位，子串[a,aa,aaa],直接算aaa的前缀和后缀的最大长度len("aa")=2,next[3]=2

2.  s="abaabcac"对应的next值为{-1 0 0 1 1 2 0 1} or {0 1 1 2 2 3 1 2}

第一位next[1]=-1

第二位b对应的子串只有a，长度为0，next[2]=0

第三位a对应的子串a，ab，ab的前缀后缀无共有元素，长度为0，next[3]=0

第四位a对应的模式子串，这里直接算aba，aba的前缀后缀共有元素a，长度为1，next[4]=1

第五位b对应的模式子串，直接算abaa，前缀[a,ab,aba],后缀[baa,aa,a],共有元素a，next[5]=1

第六位c对应的子串，直接算abaab，前缀[a,ab,aba,abaa],后缀[baab,aab,ab,b],共有元素ab，长度为2，next[6]=2

第七位a对应的子串，直接算abaabc，其前缀和后缀都没有共有元素，next[7]=0

第八位c对应的子串，直接算abaabca，其前缀和后缀只有共有元素a，next[8]=1

三. C++递归求next数组

这里的next数组的解法是根据定义求取，仅给出代码不作解释：

#include<iostream>
#include<string>

using namespace std;

//get the next array of pattern string
void getnext(string &p,int next[])
{
	int length=p.length();
	//int next[length];
	int j=0,k=-1;
	//初始化next数组第一个值，k表示next数组的值，即失配字符j之前的子串中前缀和后缀最大的长度值
	next[0]=-1;
	//计算next[j]
	while(j<length-1)
	{	
		//根据定义：k=next[k],p[k]==p[j]时，next[j+1]=next[k]+1,
		//且保证p[j+1]!=p[next[j+1]]则匹配成功,否则继续递归寻找
		if (k==-1 || p[j]==p[k])
		{
			j++;
			k++;
			if(p[j]!=p[k])//此时j=j+1，k=next[k]+1
				next[j]=k;
			else
				next[j]=next[k];
		}
		else
			k=next[k];
	}
	//return next;
}
void main()
{
	string p="abc";
	int * next = new int[p.length()];
	getnext(p, next);
	for(int i=0;i < p.length(); i++)
		cout<<p[i]<<'\t'<<next[i]<<endl;
	delete []next;
}

四. KMP算法实现

直接上代码，返回的是模式串匹配成功时在主串的位置

#include<iostream>
#include<string>

using namespace std;

//get the next array of pattern string
void getnext(string &p,int next[])
{
	int length=p.length();
	//int next[length];
	int j=0,k=-1;
	//初始化next数组第一个值，k表示next数组的值，即失配字符j之前的子串中前缀和后缀最大的长度值
	next[0]=-1;
	//计算next[j]
	while(j<length-1)
	{	
		//根据定义：k=next[k],p[k]==p[j]时，next[j+1]=next[k]+1,
		//且保证p[j+1]!=p[next[j+1]]则匹配成功,否则继续递归寻找
		if (k==-1 || p[j]==p[k])
		{
			j++;
			k++;
			if(p[j]!=p[k])//此时j=j+1，k=next[k]+1
				next[j]=k;
			else
				next[j]=next[k];
		}
		else
			k=next[k];
	}
	//return next;
}

//返回主串中模式串与其匹配成功时第一个字符位置
int Kmpsearch(string &src,string &p,int k,int next[])
{
	
	//从主串的第k个字符开始搜索，
	int index_s = k, index_p = 0;
	int length_s = src.length();
	int length_p = p.length();
	
	while(index_s < length_s && index_p < length_p)
	{
		if (index_p == -1 || p[index_p] == src[index_s])
		{
			index_s++;
			index_p++;
		}
		//如果index_s != -1,且src[index_s] != p[index_p],即匹配失败，则令index_s保持不变，index_p=next[index_p]；
		else
			index_p = next[index_p];
	}
	if (index_p==length_p)
		return index_s-index_p;
	else
		return -1;
}

void main()
{
	string src="abaacabcd",p="abc";
	//cout<<"please input two string:"<<endl;
//	cin>>src;
	//cin>>p;
	int k=0;	
	int * next = new int[p.length()];
	getnext(p, next);
	for(int i=0;i < p.length(); i++)
		cout<<p[i]<<'\t'<<next[i]<<endl;
	k = Kmpsearch(src,p,k,next);
	cout<<k<<endl;
	delete []next;
}


 

参考文献：

http://www.cnblogs.com/buyongsu/p/5849798.html

http://blog.csdn.net/wusecaiyun/article/details/49281627