next和nextval的区别就是nextval就是next的优化，但是他们大部分相同。

这两个数组就是出现不匹配的情况的时候，j指针要移动到那个位置（j就是子串的指针）

next数组的算法原理还没理解，先借鉴大佬的博客（http://blog.csdn.net/guo_love_peng/article/details/6618170）

poj 3461

#include <stdio.h>

#include <iostream>

#include <string.h>

using namespace std;

int nxt[10005];

char p[10005];

char s[1000005];

void getnext() //获得next数组

{

    nxt[0]=-1;

    int i=0;

    int j=-1;

    int pl=strlen(p);

    while(i!=pl)

    {

        while(j!=-1&&p[i]!=p[j]) j=nxt[j];

        nxt[++i]=++j;

    }

}

int kmp()

{

    int sum=0;

    int pl=strlen(p);

    int sl=strlen(s);

    int i=0,j=0;

    while(i!=sl&&j!=pl)

    {

        if(j==-1||s[i]==p[j])//j==-1的意思 就是子串的第一个也不匹配 则j就变成nextj （next0 就是默认-1）所以我们要i++，j变成第一个再重新开始匹配

        {

            i++;

            j++;

        }else j=nxt[j];

        if(j==pl)

        {

            j=nxt[j];

            sum++;

        }

    }

    return sum;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        memset(nxt,0,sizeof(nxt));

        scanf("%s%s",p,s);

        getnext();

        printf("%d\n",kmp());

    }

    return 0;

}