KMP算法详解

问题描述

指定文本串：aabaabaaf和形式串：aabaaf

使用KMP算法判别形式串是否在文本串中呈现过？

假定形式串的长度小于文本串

思路解析

BF算法的问题是：形式串现已匹配到最终一位了发现不一样，需求将文本串和形式串的指针都往后退，导致有许多的重复匹配，功率很低。

KMP算法的思路是，在发现某个字符不匹配的时分，充分使用前面现已匹配过的成果，不要把“搜索指针”回退到现已比较过的方位，而是把形式串往后移动到适宜的方位持续比较。KMP算法只需求对文本串搜索一次，时刻复杂度是O(n)。

检索过程图解

如上图所示，在遇到不匹配的时分，依靠“部分匹配表”可知，最终一个匹配字符a对应的部分匹配值是2，可以根据下面的公式计算出形式串的移动位数。

移动位数 = 现已匹配的字符串长度 – 对应的部分匹配值

aabaa是现已匹配的字符串，长度是5；aabaa对应的部分匹配值是2，因而将形式串往右移动3位，就可以持续匹配了，KMP便是通过这个“部分匹配表”避免了搜索指针的回退。

部分匹配表

要了解部分匹配表，需求了解两个概念：前缀子串、后缀子串

• 前缀子串：包括首字母，不包括尾字母的一切子串
• 后缀子串：包括尾字母，不包括首字母的一切子串

例如：单词”bread”

• 前缀子串：”b”,”br”,”bre”,”brea”
• 后缀子串：”d”,”ad”,”ead”,”read”

部分匹配表中的数值含义是：当时这个字符前面的字符串中，持平的前缀子串和后缀子串的最大的长度。计算下aabaa的部分匹配表：

• a：前缀子串调集和后缀子串调集都是空集，持平的前后缀子串的最大长度是0
• aa：前缀子串调集是[a]，后缀子串调集是[a]，持平的前后缀子串的最大长度是1
• aab：前缀子串调集是[a,aa]，后缀子串调集是[b,ab]，持平的前后缀子串的最大长度是0
• aaba，前缀子串调集是[a,aa,aab]，后缀子串调集是[a,ba,aba]，持平的前后缀子串的最大长度是1
• aabaa，前缀子串调集是[a,aa,aab,aaba]，后缀子串调集是[a,aa,baa,abaa]，持平的前后缀子串的最大长度是2
• aabaaf，前缀子串调集是[a,aa,aab,aaba,aabaa]，后缀子串调集是[f,af,aaf,baaf,abaaf]，持平的前后缀子串的最大长度是0

“部分匹配表”的实质是，形式字符串中有时会有重复的子串，例如：aabaa的左右两边都有aa，那么该字符串的部分匹配值便是2，那么在发现aabaaf中的f不匹配的时分，只需求将aabaaf这个形式串往右移动3个方位，就可以让第一个aa来到第二个aa的方位。

代码实现

package org.javaadu.string;
import java.util.List;
public class StringSearchDemo {
    public static void main(String[] args) {
        String text = "aabaabaaf";
        String pattern = "aabaaf";
        boolean kmpRes = kmpSearch(text, pattern);
        System.out.println("kmpRes:" + kmpRes);
    }
    /**
     * 使用KMP算法求解pattern是否在text中呈现过
     *
     * @param text    文本串
     * @param pattern 形式串
     * @return pattern在text中呈现，则回来true，否则回来false
     */
    public static boolean kmpSearch(String text, String pattern) {
        //部分匹配数组，便是许多算法实现中的next数组
        int[] partMatchTable = buildPartMatchTable(pattern);
        //text中的指针
        int i = 0;
        //pattern中的指针
        int j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                //字符匹配，则两个指针一起后移
                i++;
                j++;
            } else if (j > 0) {
                //字符失配，则使用next数组，异动j指针，避免i指针回退
                j = partMatchTable[j - 1];
            } else {
                //pattern中的第一个字符就失配了
                i++;
            }
            if (j == pattern.length()) {
                //搜索成功
                return true;
            }
        }
        return false;
    }
    private static int[] buildPartMatchTable(String pattern) {
        //初始化
        int[] partMatchTable = new int[pattern.length()];
        int prefixLen = 0;
        next[0] = 0;
        int i = 1;
        while (i < pattern.length()) {
            //pattern[prefixLen]，表明目前最长持平子串的最终一位
            //pattern[i]，表明目前正在处理的子串的最终一位的字符
            if (pattern.charAt(prefixLen) == pattern.charAt(i)) {
                //假如它俩持平，说明找到了更长的持平子串
                prefixLen++;
                partMatchTable[i] = prefixLen;
                i++;//处理下一个i的字符
            } else {
                //假如不持平，则需求测验下更短1位的子串是否满足要求，因而这里要把再次循环测验下：只是改动prefixLen的值，不改动i的值
                prefixLen = next[prefixLen - 1];
                if (prefixLen == 0) {
                    //假如实在没有适宜的，则说明当时正在处理的子串的最长持平前后缀的长度是0
                    partMatchTable[i] = 0;
                    i++;//处理下一个i的字符
                }
            }
        }
        return partMatchTable;
    }
}

参考资料

1. www.ruanyifeng.com/blog/2013/0…
2. www.bilibili.com/video/BV1AY…
3. www.bilibili.com/video/BV1PD…