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

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 = 100005next_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] != '':        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] != '':        blen += 1    getnext(b)    i, j = 0, 0    while i < len(a) and a[i] != '':        if j == -1 or a[i] == b[j]:            i += 1            j += 1            if j >= len(b) or b[j] == '':                print(i - blen, end=' ')                j = next_arr[j]        else:            j = next_arr[j]