[模板]kmp算法

void () {
    int i, j;
    next[0] = -1;
    for(i = 1; i < m; i++) {
        j = next[i - 1];
        while(j >= 0 && B[i] != B[j + 1]) j = next[j];
        if(B[i] == B[j + 1]) next[i] = j + 1;
        else next[i] = -1;
    }
}

void kmp() {
    getNext();
    int i = 0, j = 0;
    while(i < n) {
        if(A[i] == B[j]) {	
            i++, j++;
            if(j == m) {
                printf("%dn", i - m);	//整个字符串匹配成功，返回下标
                j = next[j - 1] + 1;	//继续匹配
            }
        }else {	//单个字符不匹配，通过next数组跳转
            if(j == 0) i++;	//B串的第一个字符就不匹配，暴力i++
            else j = next[j - 1] + 1;	//有相同的前缀后缀（尽管长度可能为0），j跳转到相应位置
        }
    }
}