//求str对应的next数组

void getNext(char const* str, int len)

{

    int i = ;

    next[i] = -;

    int j = -;

    while( i < len )

    {

        if( j == - || str[i] == str[j] )   //循环的if部分

        {

            ++i;

            ++j;

            //修正的地方就发生下面这4行

            if( str[i] != str[j] ) //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系

                next[i] = j;      //之前的错误解法就在于整个判断只有这一句。

            else

                next[i] = next[j];  //这里其实是优化了后的，也可以仍是next[i]=j

            //当str[i]==str[j]时，如果str[i]匹配失败，那么换成str[j]肯定也匹配失败，

            //所以不是令next[i]=j，而是next[i] = next[j]，跳过了第j个字符，

            //即省去了不必要的比较

            //非优化前的next[i]表示前i个字符中前缀与后缀相同的最大长度

        }

        else                                 //循环的else部分

            j = next[j];

    }

}

//在目标字符串target中，字符str出现的个数

//n为target字符串的长度，m为str字符串的长度

int kmp_match(char *target,int n,char *str,int m){

    int i=,j=;  //i为target中字符的下标，j为str中字符的下标

    int cnt=;   //统计str字符串在target字符串中出现的次数

    while(i<=n-){

        if(j<||target[i]==str[j]){

            i++;

            j++;

        }

        else{

            j=next[j]; //当j=0的时候，suffix[0]=-1，这样j就会小于0，所以一开始有判断j是否小于0

        }

        //str在target中找到匹配

        if(j==m){

            cnt++;

            j=next[j];

        }

    }

    return cnt;

}

//在目标字符串target中，若存在str字符串，返回匹配成功的第一个字符的位置

int kmp_search(char *target,int n,char *str,int m){

    int i=,j=;  //i为target中字符的下标，j为str中字符的下标

    int cnt=;   //统计str字符串在target字符串中出现的次数

    while(i<n && j<m){

        if(j<||target[i]==str[j]){

            i++;

            j++;

        }

        else{

            j=suffix[j]; //当j=0的时候，suffix[0]=-1，这样j就会小于0，所以一开始有判断j是否小于0

        }

    }

    if(j>=m)

        return i-m;

    else

        return -;

}

//这里的next和前面一样，next[i]就是前面长度为i的字符串前缀和后缀相等的长度，

//即索引为i的字符失配时的前缀函数

void getNext(char *str,int m){

    memset(next,,sizeof(next));

    next[]=;

    int k=;

    for(int i=;i<=m;i++){

        while(k> && str[k]!=str[i-])

            k=next[k];

        if(str[k]==str[i-])

            k++;

        next[i]=k;

    }

}

//n为target字符串的长度，m为str字符串的长度,统计str在target中出现的个数

int match(char *target,int n,char * str,int m){

    int k=,cnt=;

    for(int i=;i<n;i++){

        while(k> && str[k]!=target[i])

            k=next[k];

        if(str[k]==target[i])

            k++;

        if(k==m){

            cnt++;

            k=next[k];

        }

    }

    return cnt;

}

//n为target字符串的长度，m为str字符串的长度

//若存在str字符串，返回匹配成功的第一个字符的位置

int match(char *target,int n,char * str,int m){

    int k=,cnt=;

    for(int i=;i<n;i++){

        while(k> && str[k]!=target[i])

            k=next[k];

        if(str[k]==target[i])

            k++;

        if(k==m){

            return i-m+;

        }

    }

    return -；

}

#define KMP_GO(X) while(k>0 && P[k]!=X[i]) k=next[k];if(P[k]==X[i])k++

//求字符串P在T中出现的次数

int kmp_match(char*T,char*P){

    int n,m,next[],i,k,c;

    n=strlen(T);m=strlen(P);

    next[]=k=;

    for(i=;i<m;i++){

        KMP_GO(P);

        next[i+]=k;//这里i表示的是字符的索引，对应的长度i+1

    }

    k=c=;

    for(i=;i<n;i++){

        KMP_GO(T);

        if(k==m){

            c++;

            k=next[k];

        }

    }

    return c;

}