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]