KMP算法总结

快来打我* 2023-10-14 08:03 8阅读 0赞

### KMP算法总结 ###

*  BF算法引导
 *   *  BF算法步骤（图片演示）
     *  代码演示
 *  KMP算法
 *   *  推next数组
     *  代码演示

# BF算法引导 #

BF算法是一个暴力的字符串匹配算法，时间复杂度是o（m\*n）  
假设主串和子串分别为  
![在这里插入图片描述][c0646979f93f4c9891e4eeb19d082792.png]

我们想要找到子串在主串的位置  
BF算法核心：**BF算法就是同时遍历子串和主串，如果不相同就将子串指针回退到首位，主串指针回退到这次遍历的起点的下一个位置**  
我们指定主串的指针为i，子串的指针为j，如下图：  
![在这里插入图片描述][83c8e221577343469fd83b7523f9865b.png]

## BF算法步骤（图片演示） ##

匹配的过程，我将用图来阐释：  
1.第一趟  
![在这里插入图片描述][81871476de0d4ddcad4ade3d434199cf.png]  
i++;  
j++;  
![在这里插入图片描述][2275c286837244af9f741213218ccaf9.png]  
i++;  
j++;  
![在这里插入图片描述][00d8140b31bb488d82653862f9168d03.png]  
这时我们发现，i和j指向的内容不一样了  
这时我们进入下一趟  
2.第二趟  
i=i-j+1;  
**(这里就是主串指针回退到这次遍历的起点的下一个位置，因为每次都是i和j同时走，但j每次都是从0开始走，j同时记录了i每次走了多少步，i-j就是回退到这一趟的起点，但这个起点我们试过了，就是+1，从下一个位置开始试)**  
j=0;  
![在这里插入图片描述][4c6dae20ef76424a879a9c8385db6d2d.png]

这里我们发现，i和j指向的内容不一样了  
这时我们进入下一趟  
3.第三趟

i=i-j+1;  
j=0;  
![在这里插入图片描述][fac2d82a9c1648f290c416025fa93bc6.png]  
i++;  
j++;  
![在这里插入图片描述][a4bd0622bba64e9c872943686beb0032.png]  
i++;  
j++;  
![在这里插入图片描述][71bd9788ba424beab61bd5b1ca7df550.png]  
这里我们发现，i和j指向的内容不一样了  
这时我们进入下一趟  
4.第四趟  
i=i-j+1;  
j=0;  
![在这里插入图片描述][95f90225fd9f48189ad6602f0505db16.png]  
这里我们发现，i和j指向的内容不一样了  
这时我们进入下一趟  
5.第五趟  
i=i-j+1;  
j=0;  
![在这里插入图片描述][99127819f5c3431fbf48f0a7180396fc.png_pic_center]  
这里我们发现，i和j指向的内容不一样了  
这时我们进入下一趟  
6.第六趟  
i=i-j+1;  
j=0;  
![在这里插入图片描述][51f883ad633240aca85bb1d8ce9db981.png]  
i++;  
j++;  
![在这里插入图片描述][51ccc5a796a048069834c56e6efd8549.png]  
i++;  
j++;  
![在这里插入图片描述][ca91c77cbdfd46c2a0e76398844f306e.png]  
i++;  
j++;  
![在这里插入图片描述][9de6c43b98c54182b4f10b6ae8683f31.png]  
i++;  
j++;  
![在这里插入图片描述][b2533f92261c4c2283944c72d09c88aa.png]  
这时我们发现主串和子串都遍历结束（这个例子有点奇怪，一般只有一个遍历结束，整个程序就能判断是否有子串，并找到子串位置）  
**我们不难发现只有当子串遍历完，才能说明主串有这个子串**

## 代码演示 ##

public class BF {
        
        static int Bf(String S,String s){
        
            //空字符串
            if(S==null||s==null){
        
                return -1;
            }
            //主串长度
            int SUM=S.length();
            //子串长度
            int sum=s.length();
            //字符串长度为0
            if(SUM==0||sum==0){
        
                return -1;
            }
            //指针
            int i=0;
            int j=0;
            while (i<SUM&&j<sum){
        
                if(S.charAt(i)==s.charAt(j)){
        
                    i++;
                    j++;
                }else {
        
                    i=i-j+1;
                    j=0;
                }
            }
            if(j>=sum){
        
                return i-j;
            }
            return -1;
        }
        public static void main(String[] args) {
        
            System.out.println(Bf("aacascscc","ac"));
        }
    }

![在这里插入图片描述][76d224ab17b34c6c93a0af2165b9f471.png]

# KMP算法 #

**KMP也是一种字符串匹配算法，只不过他利用了遍历过的串的信息，减少了趟数，最重要就是理解他怎么利用信息**  
举个例子  
![在这里插入图片描述][d259ab22a7b54278b5a3b53728e9913c.png]  
我们指定主串的指针为i，子串的指针为j，如下图：  
![在这里插入图片描述][c3bd86fafc634774a91d90c03fbe6f9a.png]  
i++；  
j++;  
一直到匹配不正确的地方  
![在这里插入图片描述][e2cc7de7bcb14cd8b53903d9a533c1f2.png]

我们想让I指针停下来，只移动j指针，（这是我们想的就是这时i要回退，我们不想让他回退，但又不能丢下前面的，所以我们看前面还有什么能用上的）这时，我们遍历了主串的ABAB ,和子串的ABAB，他们两个肯定是相同的因为刚刚遍历了，如果不相同肯定会停下来，如果是BF算法我们肯定会i=i-j+1;j++;但现在我们想利用我们遍历过的ABAB的信息，我的方法是向后拖拽子串，只要发生拖拽，主串的开头A和子串结尾的B肯定是用不上了，我们必须求的是主串的（从后面开始，如果是从BAB开始算前缀即使前面匹配后面不匹配也没有用）后缀和子串的（从前面开始）前缀，**（这里就是为什么求主串的后缀和子串的前缀）**  
![在这里插入图片描述][00533b6ffb0e424f8e48bceaf193e2b4.png]  
![在这里插入图片描述][fb466e812b5d4598a57a96260ace2dee.png]  
拖拽两次，我们发现主串和子串有AB重叠，这时我们就能继续遍历了（我的思考是这里我们利用了ABAB重叠的信息，省去了i指针回退到主串的下标为2，子串下标为0的地方一点点++匹配，而主串前面AB我们发现没有匹配，所以就丢弃）  
![在这里插入图片描述][926932cb84d447c9b94fefe8fb44d70f.png]  
现在我们想知道怎么利用匹配过的信息，怎么一下就能找到拖拽后j到的位置  
就要引入next数组，来存储j指针在每个位置匹配失败要回退到哪

## 推next数组 ##

假设有这样一个字符串  
![在这里插入图片描述][c4183e2c60274f1792f301dd0ac440c4.png]  
规则如下：  
![在这里插入图片描述][14bd9f30d38741f9a7cd57cdb02bac18.png]  
前两个下标为0，1的就是固定的，  
从下标为2开始，假设匹配失败了，ab内找以a开头以b结尾，除了本身没有这样的字符串，回退到0，  
下标为3时，假设匹配失败了，aba内找以a开头以a结尾，有这样的字符串，回退到1，  
![在这里插入图片描述][22c6039ac75e498493ffe58c7afabbb0.png]  
下标为3时，假设匹配失败了，abab内找以a开头以b结尾，有这样的字符串，回退到2，  
后面的自行计算，结果为  
![在这里插入图片描述][71812aacee134bcd9662dc304c6e3b92.png]  
给个例题，请求出他的next数组：  
![在这里插入图片描述][b04e605787e34409b11f03af0b429a06.png]  
接下来我们进行一个推理  
![在这里插入图片描述][671ce07b5f324e769be85868e4715c25.png]  
设原字符数组为p【】  
**如上图所示，next【i】=k，假设p【i】==p【k】如上图所示，那么**  
**p【0】…p【k-1】==p【x】…p【i-1】**  
**又已知k-0i-x得到xi-k**  
**p【0】…p【k-1】==p【i-k】…p【i-1】**  
**又因为p【i】==p【k】所以p【0】…p【k】==p【i-k】…p【i】**  
**所以next【i+1】==k+1**  
推出来的意思是p【8】这个前面有abc和前面的abc匹配p【3】和p【8】又相等那么p【9】找前面的匹配时直接p【8】前面找到的abc加p【8】；  
![在这里插入图片描述][3677c17840d84d1da309bb14bc7c8e63.png]  
**如上图所示，next【i】=k，假设p【i】！=p【k】如上图所示，那么**  
**不是我们要找的，我们就再回退到k=0这时p【i】==p【k】**  
**这时我们又能用next【i+1】==k+1，next【6】=k+1=1**

## 代码演示 ##

public class KMP {
        
        public static void main(String[] args) {
        
            System.out.println(KMP("CSA","SA"));
        }
            public static int KMP (String s, String sub){
        
                int lens = s.length(), lensub = sub.length();
                int[] next = new int[lensub];
                //next数组  存放匹配不上的子串要跳跃的下标
    
                getNext(next, sub);
    
                int i = 0, j = 0;
                // i 遍历主串， j 遍历子串
                while (i < lens && j < lensub) {
        
                    if (j == -1 || s.charAt(i) == sub.charAt(j)) {
        
                        i++;
                        j++;//逐一比较，相同的看下一个
                        //当子串的第一个字符就与主串的字符不相等时，j++为0，i向后移动一位
                    } else {
        
                        j = next[j];
                    }
                }
                if (j == lensub) {
        
                    return i - j;
                    //上面while循环结束条件是因为   遍历发现子串所有均与主串相等
                } else {
        
                    return -1;
                }
            }
            public static void getNext ( int[] next, String sub){
        
                next[0] = -1;
                next[1] = 0;
                //固定
    
                int i = 2;//i表示当前所求next数组的下标
                int k = 0;//比较是否相等的前一项
                while (i < sub.length()) {
        
                    if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) {
        
                    //就是一直回退直到就是说没有利用的重叠部分就是k=-1
                        next[i] = k + 1;//当k==-1时，证明【0】与【j-1】里无相等字符，k++为0，i移向下一位
                        k++;
                        i++;
                    } else {
        
                        k = next[k];
                    }
                }
            }
    
    
    }

之后如果有新的想法会及时补充，大家如果有不同见解欢迎评论区留言  
![在这里插入图片描述][3debffd776774c29bd561d504fcd9463.png_pic_center]

[c0646979f93f4c9891e4eeb19d082792.png]: https://img-blog.csdnimg.cn/c0646979f93f4c9891e4eeb19d082792.png
[83c8e221577343469fd83b7523f9865b.png]: https://img-blog.csdnimg.cn/83c8e221577343469fd83b7523f9865b.png
[81871476de0d4ddcad4ade3d434199cf.png]: https://img-blog.csdnimg.cn/81871476de0d4ddcad4ade3d434199cf.png
[2275c286837244af9f741213218ccaf9.png]: https://img-blog.csdnimg.cn/2275c286837244af9f741213218ccaf9.png
[00d8140b31bb488d82653862f9168d03.png]: https://img-blog.csdnimg.cn/00d8140b31bb488d82653862f9168d03.png
[4c6dae20ef76424a879a9c8385db6d2d.png]: https://img-blog.csdnimg.cn/4c6dae20ef76424a879a9c8385db6d2d.png
[fac2d82a9c1648f290c416025fa93bc6.png]: https://img-blog.csdnimg.cn/fac2d82a9c1648f290c416025fa93bc6.png
[a4bd0622bba64e9c872943686beb0032.png]: https://img-blog.csdnimg.cn/a4bd0622bba64e9c872943686beb0032.png
[71bd9788ba424beab61bd5b1ca7df550.png]: https://img-blog.csdnimg.cn/71bd9788ba424beab61bd5b1ca7df550.png
[95f90225fd9f48189ad6602f0505db16.png]: https://img-blog.csdnimg.cn/95f90225fd9f48189ad6602f0505db16.png
[99127819f5c3431fbf48f0a7180396fc.png_pic_center]: https://img-blog.csdnimg.cn/99127819f5c3431fbf48f0a7180396fc.png#pic_center
[51f883ad633240aca85bb1d8ce9db981.png]: https://img-blog.csdnimg.cn/51f883ad633240aca85bb1d8ce9db981.png
[51ccc5a796a048069834c56e6efd8549.png]: https://img-blog.csdnimg.cn/51ccc5a796a048069834c56e6efd8549.png
[ca91c77cbdfd46c2a0e76398844f306e.png]: https://img-blog.csdnimg.cn/ca91c77cbdfd46c2a0e76398844f306e.png
[9de6c43b98c54182b4f10b6ae8683f31.png]: https://img-blog.csdnimg.cn/9de6c43b98c54182b4f10b6ae8683f31.png
[b2533f92261c4c2283944c72d09c88aa.png]: https://img-blog.csdnimg.cn/b2533f92261c4c2283944c72d09c88aa.png
[76d224ab17b34c6c93a0af2165b9f471.png]: https://img-blog.csdnimg.cn/76d224ab17b34c6c93a0af2165b9f471.png
[d259ab22a7b54278b5a3b53728e9913c.png]: https://img-blog.csdnimg.cn/d259ab22a7b54278b5a3b53728e9913c.png
[c3bd86fafc634774a91d90c03fbe6f9a.png]: https://img-blog.csdnimg.cn/c3bd86fafc634774a91d90c03fbe6f9a.png
[e2cc7de7bcb14cd8b53903d9a533c1f2.png]: https://img-blog.csdnimg.cn/e2cc7de7bcb14cd8b53903d9a533c1f2.png
[00533b6ffb0e424f8e48bceaf193e2b4.png]: https://img-blog.csdnimg.cn/00533b6ffb0e424f8e48bceaf193e2b4.png
[fb466e812b5d4598a57a96260ace2dee.png]: https://img-blog.csdnimg.cn/fb466e812b5d4598a57a96260ace2dee.png
[926932cb84d447c9b94fefe8fb44d70f.png]: https://img-blog.csdnimg.cn/926932cb84d447c9b94fefe8fb44d70f.png
[c4183e2c60274f1792f301dd0ac440c4.png]: https://img-blog.csdnimg.cn/c4183e2c60274f1792f301dd0ac440c4.png
[14bd9f30d38741f9a7cd57cdb02bac18.png]: https://img-blog.csdnimg.cn/14bd9f30d38741f9a7cd57cdb02bac18.png
[22c6039ac75e498493ffe58c7afabbb0.png]: https://img-blog.csdnimg.cn/22c6039ac75e498493ffe58c7afabbb0.png
[71812aacee134bcd9662dc304c6e3b92.png]: https://img-blog.csdnimg.cn/71812aacee134bcd9662dc304c6e3b92.png
[b04e605787e34409b11f03af0b429a06.png]: https://img-blog.csdnimg.cn/b04e605787e34409b11f03af0b429a06.png
[671ce07b5f324e769be85868e4715c25.png]: https://img-blog.csdnimg.cn/671ce07b5f324e769be85868e4715c25.png
[3677c17840d84d1da309bb14bc7c8e63.png]: https://img-blog.csdnimg.cn/3677c17840d84d1da309bb14bc7c8e63.png
[3debffd776774c29bd561d504fcd9463.png_pic_center]: https://img-blog.csdnimg.cn/3debffd776774c29bd561d504fcd9463.png#pic_center