字符串搜索算法：暴力搜索，KMP

ゝ一纸荒年。 2024-03-16 09:36 30阅读 0赞

#### 目录 ####

*  前言废话
 *  暴力搜索
 *  KMP算法

## 前言废话 ##

最近脑子有点昏昏沉沉，喝点那种红枣泡的白酒居然神奇的好了一些，感觉很舒服。看来喝少量的酒可以让人更清醒，长期喝可能有养生的效果？ 写道这里去百度了下，发现红枣还真有养生效果。对于长期坐在电脑旁的人，不止眼睛，其实整个身体状况就注定不会很好，平时还是要注意养生。虽然现在整个行业很卷又是互联网的寒冬，但还是尽量抽出一点时间出去走走运动运动，这样人更精神做事效率也会更高。前段时间有个大佬左耳朵才40多岁就心梗去世了，应该是平时没注意自己身体或者没有精力管自己的身体健康问题？从某种程度上来说，程序员这个职业已经是一种高危职业了，有中年失业危机以及伴随的中年死亡危机。。  
  虽然这行各种危机，但是单纯的写代码还是能够从中获得乐趣，这算是代码给人的一点福利吧。

## 暴力搜索 ##

废话说完回到正题，说到字符串搜索，最简单直接的大家都能想到的一种:暴力搜索。但是这种搜索算法大家都知道它的效率是比较低的，时间复杂度O(M \* N)。

暴力搜索过程，如下图：

![在这里插入图片描述][04ea6dcef6d34679af922f5b2788a980.gif_pic_center]

代码：

public boolean searchStr(String text,String p){
        
            if(text == null || text.equals("")|| p == null||p.equals("") )return false;
            int i = 0,j = 0;
            while (i <text.length()) {
        
                if(text.charAt(i) == p.charAt(j)){
        
                    if(j == p.length()-1){
        
                        System.out.println("找到了："+text.substring(i-j,i+1));
                        return true;
                    }
                    j++;
                    i++;
                }else{
        
                    i= i-j+1;
                    j=0;
                }
            }
            return false;
        }

从上面的动态图可以看出来，暴力搜索做了很多重复搜索的工作。还是以动态图的数据为例：

![在这里插入图片描述][290cee56d1704494a7af6f6ee761abd0.png_pic_center]  
  字符串匹配了：edc三个字符最后一个没有匹配上。又要从已经搜索过的字符串中再重新比对，这就导致了在文本搜索的过程中存在大量的重复搜索过程。如果在一个大型文本中搜索特定的字符串，用这个算法来做搜索那就是一个灾难了。

## KMP算法 ##

上面提到暴力搜索算法效率低的原因是，要重复搜索已经搜索过的字符。那有没有一种算法可以解决这个问题呢？KMP算法就是解决这个问题的一种方法。KMP算法搜索文本的指针只会一直向前不会回退，这就解决了暴力搜索时指针回退造成的重复搜索问题。

![在这里插入图片描述][3ccc86154e634b3b8e37230d78f5f2cd.png_pic_center]  
  在kmp算法遇到字符串没有被完全匹配时，要求`k指针`回到正确的位置，而指向文本的`指针i`保持不变。然后继续比较p\[k\]与text\[i\]的值。

**问题：如何找到模式串P匹配失败之后 `指针K`应该回到哪个位置上呢？**

![在这里插入图片描述][4e4a40b941134ad885394f9de4d6ccc9.png_pic_center]  
  在这个例子中abab匹配了，那应该如何移动呢？看上图，就是找到`p【abab】`与`text【abab】`最长能匹配多少。这里其实就是找字串【abab】的最长公共前后缀。至于为什么要找这个后面会举例说明；先简单说下什么是前缀，后缀。

以abcab为例：

*  **前缀**：a , ab ,abc ,abca.这些都是abcab的前缀。有一个共同点：必须有第一个字符，并且不能包含最后一个字符。
 *  **后缀**：b,ab,cab,bcab.都是abcab的后缀。后缀特点：必须包含最后一个字符，并且不能有第一个字符。
 *  **最长公共前后缀**：就是找出前后缀中相同字符串，在这些相同的串中找到最长的那个。

举一个例子：

![在这里插入图片描述][29f083ca1def44dc8bd2357c98a54305.png_pic_center]

在这个例子中，text\[4\] != p\[4\],因此指向p的指针要回退。`现在假设指向p的指针可以回退到下标为3的位置，那么它必须满足p[0,2] = text[1,3]，只有这部分相同才能继续往后面比较`。

在kmp算法中要解决的问题是指向文本text的指针不能回退，因此只能回退指向p的指针，让p\[0，3\]的前缀字符串去匹配text\[0,3\]的后缀字符串。而p\[0,3\] = text\[0,3\];因此text\[0,3\]的后缀就等于p\[0,3\]的后缀； 其实就是求p\[0,3\]的公共前后缀。

上面那段话比较绕，是理解kmp算法的关键点之一。再明白了这个点之后，剩余的部分就比较容易了。

对于任意字符串p来说，与文本匹配时，可能会匹配上任意个字符。可能匹配：0，1，2，3。。。\[p.leng()\]个。如果匹配了n个字符那么就要计算p\[0,n\]的最长公共前后缀。

举个例子：p = ababc，那么要计算的字符有：a,ab,aba,abab要分别将这几个字符串的最长公共前后缀计算出来。其中 ：a只有一个字符不满足前缀，后缀的定义，因此没有公共前后缀。

public int[] next(String p){
        
            int[] next = new int[p.length()];
            if(p.length() <2)return next;
            int i = 1,k =0;
            while (i < p.length()) {
        
                if(p.charAt(i) == p.charAt(k)){
        
                    k++;
                    next[i++] = k;
                }else {
        
                    if(k ==0)i++;
                    else k=0;
                }
            }
            return next;
        }
    
        public boolean kmp(String text,String p){
        
            int[] next = next(p);
            int k = 0;
            int searchCount = 0;
            for(int i = 0;i <text.length(); ){
        
                searchCount++;
                if(text.charAt(i) == p.charAt(k)){
        
                    if(k == p.length()-1){
        
                        System.out.println("kmp搜索次数："+searchCount);
                        return true;
                    }
                    k++;
                    i++;
                }else{
        
                    if(k!= 0)
                         k = next[k-1];
                    else
                        i++;
                }
            }
            System.out.println("kmp搜索次数："+searchCount);
            return false;
        }

求next数组有点技巧，但是不太好用语言来描述，我当时是手动画图来理解next应该怎样生成。想了很久也没有想出一个通俗易懂的方式来表达，可能最好的方式就是画图理解吧。至于kmp的主体搜索过程就很简单了，和暴力搜索过程差不多，不过不用回退文本指针i，并且k指针，也是直接用next数组可以得到。

[04ea6dcef6d34679af922f5b2788a980.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b79713d7531140198339424d22c9ddae.png
[290cee56d1704494a7af6f6ee761abd0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/2fd3e452feb7477692c1261408028846.png
[3ccc86154e634b3b8e37230d78f5f2cd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6007fc7cc3fb4825b1be558526dc0288.png
[4e4a40b941134ad885394f9de4d6ccc9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/fec2d87039ca45e6ac13febd9a7bfefd.png
[29f083ca1def44dc8bd2357c98a54305.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7b42dc495f5645949e994c659f739170.png