KMP算法

如烟花般绚烂却又稍纵即逝

发布于 2024-11-26 08:36:47

2440

文章被收录于专栏：javajava

KMP算法是一种改进的字符串匹配算法，它的核心是来减少匹配次数来达到快速匹配的效果

与暴力算法（BF）不同,暴力算法是需要我们从我们从字符串中找到子串

BF算法链接

KMP算法核心是减少匹配次数来达成最终的匹配

这里我们画图来理解一下，第一个为字符串，需要与第二个字符串进行匹配，这里我们a1字符串如果与a2字符串相同的话和BF算法相同,直到找到不相同的字符串.

这里我们的字符串匹配不成功，KMP算法是我们的a1中的字符串不会进行重置或者回退，只有两个字符相匹配来寻找下一个字符串

KMP算法中因为我们需要匹配的字符串一定是比我们的总串要短或者是相同的，所以由a2进行匹配来回退到一个特定的位置.

这里a2如果不相同的话我们已经知道我们前面已经匹配了五个字符，如果匹配不成功的话我们要返回到第几个字符继续匹配呢？

可以看到因为i-1的位置可以匹配我们arr2中的a b是相同的，距离为2，j回退到下标为2的位置（在arr1中字符串与arr2中之前匹配的相同时）

这里我们定义一个next数组，用来保存子串某一个位置匹配失败后应该回退的位置，因为我们已经知道下标5中的字符a与c没有匹配成功，j需要回退，而我们回退的位置是需要尽可能的与arr1中一部分字符想匹配，所以下标5中next数组需要退回到我们的下标的2号位置.

nextj=k,回退到k位置

手动求next数组

KMP函数

  public static int KMP(String str,String sub,int pos){
    if(str==null||sub==null) return -1;
    int lenStr=str.length();
    int lenSub=sub.length();
    if(lenStr==0||lenSub==0) return -1;
    if(pos<0||pos>=lenStr) return -1;
    int[]next=new int[lenSub];
    getNext(sub,next);

    int i=pos;//遍历主串
    int j=0;//遍历子串
        while(i<lenStr&&j<lenSub){
            if(j==-1||str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            }else{
                j=next[j];//next[j]中存放了回退的位置
            }
        }
        if(j>=lenSub){
            return i-j;
        }
        return -1;
    }

getNext函数

public static void getNext (String sub,int[] next){
        next[0]=-1;
        next[1]=0;
        int i=2;//这里的i提前走了一步，不是从下标1开始从2开始了
        //
        int k=0;
        //遍历子串信息
        for(;i<sub.length();i++){
        if(k==-1||sub.charAt(i-1)==sub.charAt(k)){
            next[i]=k+1;
            i++;
            k++;
        }else{
        k=next[k];
        }
        }
    }

代码实现

public class test {
    /**
     *
     * @param str  主串信息
     * @param sub   子串信息
     * @param pos   从子串中的pos位置来寻找进行匹配
     * @return 子串在主串中首元素的下标
     */
    public static int KMP(String str,String sub,int pos){
    if(str==null||sub==null) return -1;
    int lenStr=str.length();
    int lenSub=sub.length();
    if(lenStr==0||lenSub==0) return -1;
    if(pos<0||pos>=lenStr) return -1;
    int[]next=new int[lenSub];
    getNext(sub,next);

    int i=pos;//遍历主串
    int j=0;//遍历子串
        while(i<lenStr&&j<lenSub){
            if(j==-1||str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            }else{
                j=next[j];//next[j]中存放了回退的位置
            }
        }
        if(j>=lenSub){
            return i-j;
        }
        return -1;
    }
    public static void getNext (String sub,int[] next){
        next[0]=-1;
        next[1]=0;
        int i=2;//这里的i提前走了一步，不是从下标1开始从2开始了
        //
        int k=0;
        //遍历子串信息
        for(;i<sub.length();i++){
        if(k==-1||sub.charAt(i-1)==sub.charAt(k)){
            next[i]=k+1;
            i++;
            k++;
        }else{
        k=next[k];
        }
        }
    }
    public static void main(String[] args){
        System.out.println(KMP("ababcabcda","abcd",0));
        System.out.println(KMP("ababc","abcdf",0));
        System.out.println(KMP("ababcabcd","ab",1));
    }
}