字符串匹配：KMP算法

#define MAX 100

void Next(char str[], int *next){              //next数组：记录当前位置前匹配成功的最大前缀数
    int i = 0, j = -1;
    int len = strlen(str);
    next[0] = -1;
    while(i < len) {
        if (j == -1 || str[i] == str[j])
            next[++i] = ++j;
        else
            j = next[j];                       //回到当前位置前所匹配的最大前缀
    }
}

int KMP(char str1[], char str2[]){          //字符串匹配（KMP算法）
    int i = 0, j = 0;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int *next = new int[MAX];
    Next(str2, next);                       //接收next数组
    while(i < len1 && j < len2){
        if(str1[i] == str2[j] || j == -1){  //当前匹配成功：两串均右移
            i++;
            j++;
        }
        else
            j = next[j];                    //当前匹配失败：子串回到当前位置前所匹配的最大前缀
    }
    if(j == len2)                           //字串遍历结束返回所在位置
        return (i - j);
    else
        return -1;
}