KMP 算法：快速匹配字符字串

👏 Hi! 我是 Yumuing，一个技术的敲钟人

👨‍💻 每天分享技术文章，永远做技术的朝拜者

📚 欢迎关注我的博客：Yumuing's blog

KMP 算法主要是在一定长度的字符串中快速匹配出所需的目标字符串，也称模式字串，最大特点就是讲究一个快字。

一般是适用于字符串进行比对或者匹配的场景之下，基本概括为在字符串不匹配，需进行下一次匹配时，利用已知的已匹配的字符串（文本内容）避免从头开始匹配带来的浪费。

如果是暴力解决的话，步骤如下：

1. 定义头指针以及字符指针，分别指向定长字符串最左端、模式字符串最左端
2. 依次对字符进行比较，
3. 发现不匹配字符，回溯指针到指针开始匹配的下一位
4. 重复第二步，直至找到对应字符串，即模式字符串

使用暴力解法，效率低下的主要原因即是指针回溯的位置不恰当，重复匹配操作。

前置概念

最长公共前后缀

所谓前缀、后缀的区别，简单就是说以某结点区域为分割，前一部分（不包含最后一个字符）就为前缀，后一（不包含匹配失败的部分以及第一个字符）部分为后缀。

在理解最长公共前后缀之前，得清楚公共前后缀的概念。公共前后缀简单说明，可认为是模式字符串的前某部分字符与后某字符中间部分为结点分割的区域。

最长公共前后缀就是在公共前后缀的基础上，寻找最长的部分（即使能够等于其本身，也不取其为最长，无法进行移动，故选其本身少一位为最长），即使是没有结点分割区域也可。

示例图的公共前后缀为 ABAB ，而非 ABABA

前缀表

前缀表就是保存前缀部分的长度信息及其模式字符串的对应字符位置，以便发生不匹配情况之时，通过对前缀表的内容，能够给出重新开始匹配字符串的位置信息，简单说就是匹配失败，回退字符串，重新开始。

该表中长度代表公共前后缀长度，next 代表下一次匹配时，模式字符串开始的位置，为下标值。此处我们可以知道其公共前后缀长度与 next 的值一致。

当然，对于 next 数组的值也有多种看法，有时候会将模式字符串的下标从零开始，即整体向右移一位，在制作 next 数组时，符合通常思维，第几位对应下标值为几。

实现 KMP 算法需要进行已匹配字符串的区域切割，保证不做重复的操作，而这就与前缀表的使用不可分离。

算法思路

简单 KMP 算法思路

1. 定义头指针以及字符指针，分别指向定长字符串最左端、模式字符串最左端
2. 开始对字符依次匹配，直至匹配失败的字符位置停止
3. 对已匹配的模式字符串寻找最长公共前后缀字符串
4. 若不能找到,直接移动字符指针到模式字符串最左端，重新开始匹配
5. 若能找到，将公共前后缀中的前缀部分后移到后缀部分，
6. 此时，字符指针就从原本指向后缀部分下一位指向前缀部分下一位
7. 模式字符串长度长于剩余字符串的长度，匹配失败，
8. 否则从第二、三步继续开始匹配
9. 最后，找到字符或者匹配失败

如下即为无最长前后缀的情况

利用 next 表优化

1. 先对模式字串进行每个字符的最长公共前缀长度进行计算并进行处理，再存进对应数组，即为 next 数组
2. 定义指针，开始匹配
3. 当遇到不匹配时，读取当前字符的 next 数组对应值，作为字符指针的起始位置，重新从第二步开始
4. 直至匹配成功，或模式字符串长度长于剩余字符长度，即匹配失败

算法代码

构造 next 数组

1. 初始化

   1. 定义两个指针。
      1. 此时，起始默认前后缀为模式字符串第一个字符，长度为 1 ，
      2. 第一个指针 frist 指向前缀最后一个元素，即 length - 1 初始化为 0，可知前缀为 [0,first) ；
      3. 第二个指针 last 指向后缀最后一个元素，初始化为 1 即为 length，可知后缀为 ( first,last]。
      4. frist 指针在结束之时指向的位置即为 next 数组的对应值
   2. 初始化 next 数组长度为模式字符串的长度减一，再初始化 next[0] = 0;

2. 处理前后缀不同的情况

   1. string[frist] != string[last] ,多次回退为 while 并且为保证 frist-1 不越界，判断条件必须为 frist > 0 && string[frist] != string[last]
   2. 如果末尾字符不相等，多次回退到前一个字符的 next 数组对应值，即 frist = next[frist-1]

3. 处理前后缀相同的情况

   1. string[frist] == string[last]
   2. first ++

1. 更新 next数组的值
   1. 每一次 last 迭代，即 last ++ 前
   2. 记录此时 next 对应值: next[last] = first;

最终代码

    //target 为模式字符串，string 为定长字符串
    //当匹配成功时，返回在定长字符串中的与模式字符串一致的字符串起始下标
    //匹配失败返回 -1
    public static void getNext(int[] next,char[] target){
   
        int frist = 0;
        next[0] = 0;
        for(int last = 1;last < target.length; last++){
   
            while(frist > 0 && target[frist] != target[last]){
   
                frist = next[frist-1];
            }
            if(target[frist] == target[last]){
   
                frist++;
            }
            next[last] = frist;
        }
    }
    public static int getFristStr(char[] target,char[] string){
   
        if(target.length == 0){
   
            return 0;
        }
        int next[] = new int[target.length];
        getNext(next,target);
        int targetPointer = 0;
        for(int stringPointer = 0; stringPointer < string.length; stringPointer++){
   
            while(targetPointer > 0 && target[targetPointer] != string[stringPointer]){
   
                targetPointer = next[targetPointer-1];
            }
            if(target[targetPointer] == string[stringPointer]){
   
                targetPointer++;
            }
            if(targetPointer == target.length){
   
                return (stringPointer - target.length + 1);
            }
        }
        return -1;
    }


    public static void main(String[] args){
   
        Scanner input = new Scanner(System.in);
        String str1 = input.next();
        String str2 = input.next();
        char[] string = str1.toCharArray();
        char[] target = str2.toCharArray();
        System.out.println(getFristStr(target,string));
    }