void get_next(string sub,int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while(i < sub.length)
    {
        if(j == 0 || sub.ch[i] == sub.ch[j])
        {
            i++,j++;
            next[i] = j; //若p_i == p_j 则next[j+1] = next[j]+1
        }
        else
            j = next[j]//否则令 j = next[j]
    }
}

int KMP(string s,string sub,int next[])
{
    int i = 1; j = 1;
    while(i <= s.length && j <= sub.length)
    {
        if (j == 0 || s.ch[i] == sub.ch[j])
            i++,j++;//继续比较字串
        else
            j = next[j];//模式串向右移动
    }
    if(j > sub.length)
        return i-sub.length;//匹配成功
    else 
        return 0;
}

void get_nextval(string sub,int nextval[])
{
    int i=1,j=0;
    nextval[1] = 0;
    while(i<sub.length)
    {
        if(j==0 || sub.ch[i] == sub.ch[j])
        {
            ++i,++j;
            if(sub.ch[i]!=sub.ch[j])nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}