Java实现KMP算法的字符串匹配

我就是我 2023-10-11 17:54 34阅读 0赞

KMP算法往往是和朴素模式匹配算法相对比的，后者是一种暴力解决算法，用模式串与主串的每个子串一一比较。最终确定模式串在主串的起始位置。

主串：dfaabaafh3  
模式串：aabaa

肉眼可以看出模式串是在主串第3个字符开始出现的。如果使用朴素模式匹配算法，则一共有(n-m)+1个子串，n是主串长度，m是模式串长度。所以说需要比较(n-m)+1次。每次又需要比较m次，所以最坏的情况下，整个朴素模式匹配的算法时间复杂度是o(mn)。

KMP算法的时间复杂度可以控制在 o(m+n），核心就是kmp算法可以让主串的指针不回溯，主串的指针一直向前移动，而动态的变化模式串的指针。而动态变化模式串指针的关键就是，当遇到某一个不匹配字符时，需要找到模式串当前这个字符之前的子串的最长相等前后缀。求出最长相等前后缀的长度，最终求出当前字符的下个指针应该是 (字串长度) - （字串长度 - （模式串匹配的长度）） + 1。求某个字符前面字符的公共前后缀的长度，定义两个指针，主串指针不断移动，如果与模式串不匹配，则模式串指针重置为1。

*  求next数组代码实现如下

//获取某个模式串的next数组（整个过程就是找模式串的不匹配字符之前的字串的最长相等前后缀，找到以后将前缀
        // 移动到后缀位置，模式串指针此时等于（字串长度） - （字串长度 - 最长相等前后缀长度） + 1 ）
        private static int[] getNextArr(char[] chars) {
        
            int[] next = new int[chars.length];//存储每个字符的next指针，也是从1开始存储
            next[1] = 0;//如果第一次字符就不匹配了，则主串指针和模式串指针都需要++,但是需要先将模式串指针修改为0，再++
            next[2] = 1;//如果遇到第二个字符不匹配了，则从第一个字符开始
            //从第三个字符开始求字串的最长相等前后缀（注意,最长相等前后缀的长度不能等于子串的长度）
            int i = 3;
            while (i < chars.length) {
        
                //定义两个指针，一个指向模式串，另一个指向模式串复制出来的主串
                int modelIndex = 1;//从第一个字符开始扫描
                int mainIndex = 2;//从第一个字符开始扫描
    
                //主串的指针不能超过当前字串的长度（这里应该用主串的指针，因为模式串的指针是可能被重置为1的）
                while (mainIndex < i) {
        
                    //模式串modelIndex与主串mainIndex指进行比较，如果相等，同时++
                    char mainChar = chars[mainIndex];
                    char modelChar = chars[modelIndex];
                    if (mainChar == modelChar) {
        
                        modelIndex++;
                        mainIndex++;
                    } else {
        
                        //只让mainIndex++
                        mainIndex++;
                        modelIndex = 1;
                    }
                }
                //循环结束后，modelIndex--,算出实际的相等前缀长度
                modelIndex--;
                int nextIndex = (i - 1) - ((i - 1) - modelIndex) + 1;
                next[i] = nextIndex;
                i++;
            }
            return next;
        }

*  求模式串的位置实现代码如下

//获取模式串在主串中的位置，如果没有，则返回0（从下标1开始存元素的）
        private static int indexOf(char[] mainChar, char[] modelChar, int[] next) {
        
            //KMP算法的核心就是使得主串的指针不会回溯
            int mainCharIndex = 1;//主串的指针
            int modelCharIndex = 1;//模式串的指针
            //while循环条件
            while (mainCharIndex < mainChar.length ) {
        
                char mainc = mainChar[mainCharIndex];
                char modelc = modelChar[modelCharIndex];
                if (mainc == modelc) {
        
                    //主串和模式串相等，继续比较
                    mainCharIndex++;
                    modelCharIndex++;
                    if (modelCharIndex >= modelChar.length) {
        
                        //说明模式串已经比较完了
                        break;
                    }
                } else {
        
                    //如果不一致，则需要找到模式串当前不匹配字符的next下标
                    int nextIndex = next[modelCharIndex];
                    modelCharIndex = nextIndex;//让模式串从nextIndex开始与主串当前位置进行比较
                    if (modelCharIndex == 0) {
        
                        //如果模式串返回0，则表示第一个主串与模式串的第一个字符就不匹配，则此时需要同时++
                        modelCharIndex++;
                        mainCharIndex++;
                    }
                }
    
            }
    
            if (modelCharIndex >= modelChar.length) {
        
                //模式串指针已经全部走完了,可以匹配
                return mainCharIndex - ( modelChar.length - 1) ; //主串指针减去模式串长度
            } else {
        
                return 0;
            }
        }

这里注意，当遇到不匹配字符时，要获取这个字符处的next指针，如果指针是0，则应该让主串指针和模式串指针同时++。

*  测试代码如下

public static void main(String[] args) {
        
            char[] chars = {
        '\0', 'a', 'a', 'b', 'a', 'a', 'f'};//0处位置废弃不存储任何元素，从1开始存元素
            int[] next = getNextArr(chars);
            for (int i = 1; i < next.length; i++) {
        
                System.out.println("字符" + i + "的next  ==> " + next[i]);
            }
    
            //匹配主串
            char[] mainChar = {
        '\0', 'd', 'f', 'a', 'a', 'b','a', 'a', 'f', 'h', '3'};
            int position = indexOf(mainChar, chars, next);
            System.out.println("position = " + position);
        }

#### next数组问题 ####

*  next数组的前两个下标值都是固定的，-1，0或者是0，1，如果是-1，0，则表示模式串指针从0开始，如果是0，1，则表示模式串指针从1开始，那么当从0开始时，如果next\[j\]=-1，则表示此时主串指针和模式串指针都需要++，同理，如果时从1开始，如果next\[j\]=1，则表示主串指针与模式串指针都需要++。
 *  最长公共前后缀问题：这里注意，前缀不包含最后一个字符，后缀不包含第一个字符，且前缀与后缀的顺序都是从左往右，后缀也不是从右往左。
 *  设主串长度为n，模式串长度为m，如果是朴素模式匹配算法，则在最坏情况下，需要长度为n的主串含有长度为m的模式（n-m+1）个，每次需要比较m次，则朴素模式算法的时间复杂度为o(mn)。省略了mm+m，因为与长度为n的主串相比，模式串长度往往远远小于主串。那么对于KMP算法来说，时间复杂度主要分为，求next数组以及匹配，求next数组只和模式串长度m有关，o(m)，由于主串指针不需要回溯，那么主串匹配的时间复杂度为o(n),则整个时间复杂度为o(m+n)。