KMP原理版，动画分析，易懂：https://www.bilibili.com/video/av49930100?from=search&seid=1592349894888831761

  • BruteForce（暴力算法）
  • DFA_KMP（使用有限状态自动机）
  • KMP1（使用next数组，未优化）
  • KMP2（使用next数组，优化后）
表1 4种模式匹配算法的平均O(n)比较

这里写图片描述

因为测试数据太少，可能存在偶然情况，所以BruteForce竟然和KMP比较接近。但是可以看到，DFA_KMP和优化后的KMP明显快。

这里写图片描述

图1 4种模式匹配算法的平均O(n)比较

我对同组用例用4种算法测试，跑了10次。去掉最大、最小值后取了平均值。这个图就很清晰了，DFA在此次测试中是最稳定的，其次是优化后的KMP。

这里写图片描述

图2 4种模式匹配算法的平均O(n)比较

什么是KMP？

leetcode编程原题：Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

定义：给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

Knuth-Morris-Pratt 算法（简称 KMP）是解决这一问题的常用算法之一，这个算法是由高德纳（Donald Ervin Knuth）和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。

BruteForce是什么？

bruteforce即朴素匹配算法，也叫暴力匹配。O(n)=(n*m) n为主串长度，m为模式串长度。

用模式串从第一位和主串开始匹配，对应位置相等则，i++，j++，主串，子串都向后移位，继续匹配下一位。
对应位置不相等，则主串指针返回到第二位（主串下标从1开始），模式串则重新从开始第1位和主串匹配，重复上述过程。直到，模式串每位都和主串匹配上。
可见，这种暴力算法每次不匹配时，都要回溯到开始，而不匹配处之前的串是相匹配的，一旦回溯，也就意味着，已经匹配过的位置会重复匹配，时间就是在这个过程中浪费的。
例：主串txt：abababcdf
模式串pat：abcd
这里写图片描述

高纳德大神的KMP又是什么呢？

请移步，参考引文1……因为太长了……-_-

改进的KMP又改进了哪些地方呢？

在这之前，你需要理解，前缀、后缀、next数组这些概念。请移步参考引文2。
摘自参考引文：
KMP算法（未优化版）： next数组表示最长的相同真前后缀的长度，我们不仅可以利用next来解决模式串的匹配问题，也可以用来解决类似字符串重复问题等等，这类问题大家可以在各大OJ找到，这里不作过多表述。

KMP算法（优化版）： 根据代码很容易知道（名称也改为了nextval），优化后的next仅仅表示相同真前后缀的长度，但不一定是最长（称其为“最优相同真前后缀”更为恰当）。此时我们利用优化后的next可以在模式串匹配问题中以更快的速度得到我们的答案（相较于未优化版），但是上述所说的字符串重复问题，优化版本则束手无策。

看不懂代码怎么办？

先理解思想，最起码能手写BruteForce。DFA_KMP，KMP及优化后的KMP，先理解思想。
详情移步引文1、2，分别讲述了DFA_KMP、KMP及优化后KMP的详细过程。
另有引文3知乎大神，通俗讲解。
还有引文4印度小哥（双语版，保证听得懂），视频讲解。
ps：视频中，next数组没有向后移位1位，参考引文2，你就会知道移位是什么意思，在代码中是怎样的实现。

以下代码为java版

**先来朴素算法，也就是暴力算法**

1、BruteForce

public class BruteForce {

	public static void main(String[] args) {
		String pat = "abcdabd";
		String txt = "bbc abcdab abcdabcdabde";
		
		long startTime1 = System.nanoTime();    //获取开始时间
		int loc =search(pat, txt);
		long endTime1 = System.nanoTime();    //获取结束时间
		if(loc==txt.length())
			System.out.println("not found");
		else
		System.out.println("text:    " + txt);
		System.out.print("pattern: ");
		for (int i = 0; i < loc; i++)
			System.out.print(" ");
		System.out.println(pat);
		System.out.println("loc:" + loc);
		System.out.println("使用BruteForce，程序运行时间：" 
		+ (endTime1 - startTime1) + "ns");    //输出程序运行时间
	}
	public static int search(String pat,String txt) {
		int m = pat.length();
		int n = txt.length();
		for(int i=0;i<n-m;i++) {
			int j;
			for(j=0;j<m;j++) {
				if(txt.charAt(i+j)!=pat.charAt(j)) {
					break;
				}
					
			}
			if(j==m)return i; //found
	
		}
		return n;//not found
	}
	

}


text:    bbc abcdab abcdabcdabde
pattern:                abcdabd
loc:15
使用BruteForce，程序运行时间：11842ns

2、使用DFA有限状态自动机实现

public class DFAKMP {
    private final int R;       // the radix
    private int[][] dfa;       // the KMP automoton

    private String pat;        // the pattern string

    public static void main(String[] args) {
    	String pat = "abcdabd";
		String txt = "bbc abcdab abcdabcdabde";

        DFAKMP kmp1 = new DFAKMP(pat);
        long startTime1 = System.nanoTime();    //获取开始时间
        int offset = kmp1.search(txt);
        long endTime1 = System.nanoTime();    //获取结束时间
        // print results
        System.out.println("text:    " + txt);

        System.out.print("pattern: ");
        for (int i = 0; i < offset; i++)
            System.out.print(" ");
        System.out.println(pat);
        System.out.println("loc:"+offset);
+ (endTime1 - startTime1) + "ns");    //输出程序运行时间
    }

    public int search(String txt) {

        // simulate operation of DFA on text
        int m = pat.length();
        int n = txt.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == m) return i - m;    // found
        return n;                    // not found
    }

    public DFAKMP(String pat) {
        this.R = 256;
        this.pat = pat;

        // build DFA from pattern
        int m = pat.length();
        dfa = new int[R][m];
        dfa[pat.charAt(0)][0] = 1;
        for (int x = 0, j = 1; j < m; j++) {
            for (int c = 0; c < R; c++)
                dfa[c][j] = dfa[c][x];     // Copy mismatch cases.
            dfa[pat.charAt(j)][j] = j+1;   // Set match case.
            x = dfa[pat.charAt(j)][x];     // Update restart state.
        }
    }
}




text:    bbc abcdab abcdabcdabde
pattern:                abcdabd
loc:15
使用DFA_KMP，程序运行时间：5131ns

3、使用next数组，KMP，未优化

public class KMP {
	public static void main(String[] args) {
		int next[] = new int[100];
		int nextVal[] = new int[100];
		String pat = "abcdabd";
		String txt = "bbc abcdab abcdabcdabde";
		
		long startTime1 = System.nanoTime();    //获取开始时间
		int offset = KMP(txt, pat, next);
		long endTime1 = System.nanoTime();    //获取结束时间
		System.out.println("text:    " + txt);
		System.out.print("pattern: ");
		for (int i = 0; i < offset; i++)
			System.out.print(" ");
		System.out.println(pat);
		System.out.println("loc:" + offset);
		System.out.println("使用未优化KMP，程序运行时间：" 
		+ (endTime1 - startTime1) + "ns");    //输出程序运行时间
		System.out.println();
		}
//未优化KMP
	public static void getNext(String pat,int next[]) {
		int m = pat.length();
	    int i = 0;   // P 的下标
	    int j = -1;  
	    next[0] = -1;

	    while (i < m - 1)
	    {
	        if (j == -1 || pat.charAt(i) == pat.charAt(j))
	        {
	            i++;
	            j++;
	            next[i] = j;
	        }
	        else
	            j = next[j];
	    }	
	}
	/*Return the index of the first occurrence of pat in txt,
	 or -1 if pat is not part of txt. */
	static int KMP(String txt, String pat, int next[])
	{
	   getNext(pat, next);

	    int i = 0;  // the index of txt 
	    int j = 0;  // the index of pat
	    int n = txt.length();//txt length
	    int m = pat.length();//pat length

	    while (i < n && j < m)
	    {
	        if (j == -1 || txt.charAt(i) == pat.charAt(j))  // P 的第一个字符不匹配或 S[i] == P[j]
	        {
	            i++;
	            j++;
	        }
	        else
	            j = next[j];  // 当前字符匹配失败，进行跳转
	    }

	    if (j == m)  // 匹配成功
	        return i - j;
	    
	    return -1;
	}

}


text:    bbc abcdab abcdabcdabde
pattern:                abcdabd
loc:15
使用未优化KMP，程序运行时间：12632ns

4、使用next数组，KMP，优化后

public class KMP {
	public static void main(String[] args) {
		int next[] = new int[100];
		int nextVal[] = new int[100];
		String pat = "abcdabd";
		String txt = "bbc abcdab abcdabcdabde";
		long startTime2 = System.nanoTime();    //获取开始时间
		int offset2 = KMP(txt, pat, nextVal);
		long endTime2 = System.nanoTime();    //获取结束时间
		System.out.println("text:    " + txt);
		System.out.print("pattern: ");
		for (int i = 0; i < offset2; i++)
			System.out.print(" ");
		System.out.println(pat);
		System.out.println("loc:" + offset2);
		System.out.println("使用优化KMP，程序运行时间：" 
		+ (endTime2 - startTime2) + "ns");    //输出程序运行时间

	}
	/* 优化后KMP*/
	void getNextval(String pat, int nextval[])
	{
	    int m = pat.length();
	    int i = 0;   // P 的下标
	    int j = -1;  
	    nextval[0] = -1;

	    while (i < m - 1)
	    {
	        if (j == -1 || pat.charAt(i) == pat.charAt(j))
	        {
	            i++;
	            j++;
	          
	            if (pat.charAt(i)!=pat.charAt(j))
	                nextval[i] = j;
	            else
	                nextval[i] = nextval[j];  // 既然相同就继续往前找真前缀
	        }
	        else
	            j = nextval[j];
	    }
	}
	/*Return the index of the first occurrence of pat in txt,
	 or -1 if pat is not part of txt. */
	static int KMP(String txt, String pat, int next[])
	{
	   getNext(pat, next);

	    int i = 0;  // the index of txt 
	    int j = 0;  // the index of pat
	    int n = txt.length();//txt length
	    int m = pat.length();//pat length

	    while (i < n && j < m)
	    {
	        if (j == -1 || txt.charAt(i) == pat.charAt(j))  // P 的第一个字符不匹配或 S[i] == P[j]
	        {
	            i++;
	            j++;
	        }
	        else
	            j = next[j];  // 当前字符匹配失败，进行跳转
	    }

	    if (j == m)  // 匹配成功
	        return i - j;
	    
	    return -1;
	}

}

text:    bbc abcdab abcdabcdabde
pattern:                abcdabd
loc:15
使用优化KMP，程序运行时间：6316ns
# KMP
Logo
EazyDevelop社区

一站式 AI 云服务平台

更多推荐

cover

10分钟上手！OpenClaw Skill开发新手教程，零代码基础也能搞定

avatar EazyDevelop社区
cover

AI可视化编辑在线模板：零代码快速生成专业设计内容的实操指南

avatar EazyDevelop社区
cover

2026年生产车间生产管理系统推荐！这6款工具值得试试

avatar EazyDevelop社区