KMP算法代码模板（C/C++/Java/Python多版本）

KMP算法是一种高效的字符串匹配算法，其核心在于通过预处理模式串生成一个next数组，记录匹配失败时模式串指针应回退的位置。在匹配过程中，主串指针永不回溯，当字符失配时，模式串指针根据next值跳跃，从而避免重复比较，将时间复杂度优化至O(m+n)。

1. C/C++版代码：

const int maxn = 100005;
int next[maxn]; // next 数组
void getnext(char* s) { // 构造 next 数组
    next[0] = -1;
    int i = 0, j = -1;
    while (s[i]) {
        if (j == -1 || s[i] == s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
void kmp(char* a, char* b) { // 输出 a 中每个匹配 b 串的下标
    int blen = 0;
    while (b[blen]) blen++;
    getnext(b);
    int i = 0, j = 0;
    while (a[i]) {
        if (j == -1 || a[i] == b[j]) {
            i++, j++;
            if (!b[j]) {
                printf("%d ", i - blen);
                j = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

2. Java版代码：

public class KMP {
    static final int maxn = 100005;
    static int[] next = new int[maxn];//next数组
    
    static void getnext(char[] s){//构造next数组,真正的模板
        next[0] = -1;
        int i = 0, j = -1; //j为什么初值赋值-1其实也行,仅仅是为了少一个判断,
        while(i < s.length && s[i] != 0){
            if(j == -1 || s[i] == s[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    static void kmp(char[] a, char[] b){ //输出b中每个匹配b串的下标,不同问题这个函数的写法多变
        int blen = 0;
        while(blen < b.length && b[blen] != 0) blen++;
        getnext(b);
        int i = 0, j = 0;
        while(i < a.length && a[i] != 0){
            if(j == -1 || a[i] == b[j]){
                i++; j++;
                if(j >= b.length || b[j] == 0){
                    System.out.print((i - blen) + " ");
                    j = next[j];
                }
            }
            else j = next[j];
        }
    }
}

3. Python版代码：

maxn = 100005
next_arr = [0] * maxn #next数组

def getnext(s):#构造next数组,真正的模板
    next_arr[0] = -1
    i, j = 0, -1 #j为什么初值赋值-1其实也行,仅仅是为了少一个判断,
    while i < len(s) and s[i] != '\0':
        if j == -1 or s[i] == s[j]:
            i += 1
            j += 1
            next_arr[i] = j
        else:
            j = next_arr[j]

def kmp(a, b): #输出b中每个匹配b串的下标,不同问题这个函数的写法多变
    blen = 0
    while blen < len(b) and b[blen] != '\0':
        blen += 1
    getnext(b)
    i, j = 0, 0
    while i < len(a) and a[i] != '\0':
        if j == -1 or a[i] == b[j]:
            i += 1
            j += 1
            if j >= len(b) or b[j] == '\0':
                print(i - blen, end=' ')
                j = next_arr[j]
        else:
            j = next_arr[j]