说起来串，不过就是BF和KMP。

KMP比BF多了一个next数组，KMP降低了时间复杂度，但提高了空间复杂度。用时间换空间，自古两难全。

int BF(String S, String T, int pos) {//pos是进行模式匹配的起始位置
    int i = 0;
    int j = 0;
    int start = 0;//子串的起始位置
    if (pos < 0 || (pos + T.length >= S.length)) {//起始位置小于0或者起始位置加上模式串的长度大于主串的长度，就不用进行匹配了
        printf("Irregular position.\n");
    } else {//进行匹配
        i = pos - 1;
        while (i < S.length && j < T.length) {
            if (S.str[i] == T.str[j]) {
                if (j == 0) {
                    start = i;//记录子串的起始位置
                }
                i++;
                j++;
            } else {
                if (j != 0) {
                    i = start + 1;
                } else {
                    i = i + 1;
                }
                j = 0;
            }
        }
        if (j == T.length) {
            printf("ok\n");
            printf("start position = %d\n", start + 1);
        } else {
            printf("bu ok\n");
        }
    }

    return (start + 1);//返回子串的起始位置的逻辑位置
}

KMP 从主串s 和子串t 的第一个字符开始，将两字符串的字符一一比对，如果出现某个字符不匹配，主串回溯到第二个字符，子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配，主串回溯到第三个字符，子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。

int KMP(String S, String T, int next[]) {
    int start = 0;
    int i = 0;//主串的循环变量
    int j = 0;//模式串的循环变量

    while (i < S.length && j < T.length) {
        if (S.str[i] == T.str[j]) {//若主串和模式串的字符相同，都向后移一位
            i++;
            j++;
        } else {//若失配了，模式串的循环变量就要根据next数组回溯
            j = next[j];
            if (j == -1) {
                i++;
                j++;//j=-1时，j必须要加1，否则下标越界导致运行出错
            }
        }

    }
    if (j == T.length) {//判断匹配是否成功
        start = i - T.length + 1;
        return start;
    }
    return -1;
}
举个简单的例子，理解一下next数组的含义

求模式串t=aaab的next数组。

说说我的理解。第一个a，next【j】=-1，这是一定的，你哪个数组都是一样的。

第二个a，next【j】=0，因为它前面就一个数，没有和它一样的数存在。

第三个a，next【j】=1，因为它前面有一个a和第一个数相同。

第四个b，不言而喻，next【j】=2。

其实KMP算法还可以改进，引入一个nextval数组取代next即可。（这个考试不考，不写了）