kmp模板

构建前缀和数组

1. 当前一个字符的对称程度为0时候只需要将当前字符与子串的前一个字母进行比较就可以了
2. 如果前面一个字符的对称程度为1时，那我们就把当前字符与子串第二个字符进行对比
3. 当出现不相等的情况让j=next[j]，(最大对称的那个位置),下一次匹配就从j的下一位进行匹配

//这里p表示模式串
void getnext(char* p, int len){
    next[0] = -1;
    int j = -1, i = 0;
    while (i < len) {
        while (j != -1 && p[i] != p[j]) j = next[j];
        next[++i] = ++j;
    }
}

返回出现str1在str2中第一次出现的位置

int kmp(char* str1, char* str2){
    int len1, len2;
    int i, j;

    i = j = 0; len1 = strlen(str1), len2 = strlen(str2);
    getnext(str2, len2);

    while (i < len) {
       if (j != -1 && str1[i] != str2[j]) j = next[j];
       i++, j++;
       if (j == len2) {
           return i - len2 + 1;
       }
    }
    return -1;
}