Java-串(BF和KMP算法)

系统管理员 2023-10-02 17:42 92阅读 0赞

### BF ###

一种简单的模式匹配算法，目的是寻找模式串p是否在目标串s中有出现。

思想：先从第一个字符开始匹配，如果p\[j\]==s\[i\]，那么继续向下比较，一旦不相等，即回溯到目标串的下一个字符，重复工作。

成功条件：当循环结束时，判断j的值与模式串p的长度是否相等，如果相等，说明匹配成功到了模式p的最后一个字符。

返回值：返回模式串在目标串中出现的位置。

/**
     * 字符串模式匹配的 Brute-Force算法（暴力法）
     * @author huanmin
     *
     */
    
    public class StrMatchBF {
        
    
        /**
         * 匹配字符串
         * @param iniStr 原始字符串
         * @param patternStr 模式字符串
         * @return 如果模式字符串在原始字符串中存在，返回模式字符串在原始字符串中第一次出现的索引。
         */
        public int indexOfStr(String iniStr, String patternStr) {
        
            if(iniStr == null || iniStr.length() <= 0 ||
                    patternStr == null || patternStr.length() <=0) {
        
                return -1;
            }
    
            int iniLength = iniStr.length();
            int patternLength = patternStr.length();
            int i = 0, j = 0; //两个字符的起始下标
            while(i < iniLength && j < patternLength) {
        
                //比较两个字符串的同位置的元素
                if(iniStr.charAt(i) == patternStr.charAt(j)) {
        
                    i++;
                    j++;
                } else {
        
                    // 失配，回退 下一个索引位置
                    i = i - j + 1;
                         //匹配字符串从0开始
                    j = 0;
                }
            }
            //检测是否完全匹配完成
            if(j == patternLength) {
        
                //计算下标(模式字符串在原字符串的开始位置)
                return i - patternLength;
            } else {
        
                return -1;
            }
        }
    }

### KMP ###

KMP算法的好处就是不用回溯,还可以避免不必要的匹配！而是以一种滑动的方式匹配模式串。此算法不细讲,因为就算写了原理也看不懂.还不如你自己研究比较好

KMP运行流程:  
先看一下 KMP 算法运行流程（假设主串：ababcabcacbab，模式串：abcac）

**第一次匹配:**  
![在这里插入图片描述][38e8a0d1945c4d30b095ed3c7fd92f06.png]  
匹配失败，i 指针不动，j = 1（字符‘c’的next值）;

**第二次匹配:**  
![在这里插入图片描述][9d1207ad3c6e4efb94ccf6823a0a60de.png]  
相等，继续，直到：  
![在这里插入图片描述][a8fb0901c9bf44028f60b5f525f7bb4d.png]  
匹配失败，i 不动，j = 2 （ j 指向的字符 ‘c’ 的 next 值）;

**第三次匹配：**  
![在这里插入图片描述][c8e3ad5bdde248e4ae3e266a0ff97699.png]

相等，i 和 j 后移，最终匹配成功。

注意：对于上边的KMP算法中的next数组，不是最精简的，还能够简化。从而减少匹配的次数 (简单的来说就是跳过重复匹配)

总结:KMP 算法，之因此比 BF 算法快的根本缘由在于：KMP 算法其实也和 BF 算法同样，都是从主串开头开始匹配，可是在匹配过程当中，KMP算法记录了一些必要的信息。根据这些信息，在后续的匹配过程当中，跳过了一些无心义的匹配过程。

/**
     * 字符串匹配的KMP算法 (最快匹配法)
     *
     * @author huanmin
     */
    public class StrMatchKMP {
        
    
        public static int indexOfStrKMP(String iniStr, String patternStr) {
        
            if (iniStr == null || iniStr.length() <= 0 ||
                    patternStr == null || patternStr.length() <= 0) {
        
                return -1;
            }
    
            // 得到模式串的next数组
            int[] nextArr = getNextArray(patternStr);
            int iniLength = iniStr.length();
            int patternLength = patternStr.length();
            int i = 0;  // 原始串索引
            int j = 0;  // 模式串索引
            while (i < iniLength && j < patternLength) {
        
                if (j == -1 || iniStr.charAt(i) == patternStr.charAt(j)) {
        
                    i++;
                    j++;
                } else {
        
                    //匹配失败,取下一个匹配位置(i不动,调整j的匹配位置)
                    j = nextArr[j];
                }
            }
            if (j == patternLength) {
        
                return i - patternLength;
            } else {
        
                return -1;
            }
        }
    
        /**
         * 获取模式字符串的next数组
         *
         * @param str
         * @return
         */
        private static int[] getNextArray(String str) {
        
            if (str == null || str.length() <= 0) {
        
                return null;
            }
            int length = str.length();
            int[] nextArr = new int[length];
            nextArr[0] = -1;//跳过第一个
    
            //j>k  永远k比j少1
            int j = 0;
            int k = -1;
            while (j < length - 1) {
        
                //等于-1  或者 j=k
                if (k == -1 || str.charAt(j) == str.charAt(k)) {
        
                    // 匹配，移动
                    j++;
                    k++;
                    if (str.charAt(j) == str.charAt(k)) {
        
                        //判断移动之后,的字符串是否相等,如果相等那么j从上一个k位置进行匹配(k<j)
                        nextArr[j] = nextArr[k];
                    } else {
        
                        //如果不相等那么j,从k的位置开始匹配
                        nextArr[j] = k;
                    }
                } else {
        
                    //算出最大长度
                    k = nextArr[k];
                }
            }
            return nextArr;
        }
    }

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^\_^

![ceaefc422a4745479fc1e8cfd2bdb74e.jpg][]

[38e8a0d1945c4d30b095ed3c7fd92f06.png]: https://img-blog.csdnimg.cn/38e8a0d1945c4d30b095ed3c7fd92f06.png
[9d1207ad3c6e4efb94ccf6823a0a60de.png]: https://img-blog.csdnimg.cn/9d1207ad3c6e4efb94ccf6823a0a60de.png
[a8fb0901c9bf44028f60b5f525f7bb4d.png]: https://img-blog.csdnimg.cn/a8fb0901c9bf44028f60b5f525f7bb4d.png
[c8e3ad5bdde248e4ae3e266a0ff97699.png]: https://img-blog.csdnimg.cn/c8e3ad5bdde248e4ae3e266a0ff97699.png
[ceaefc422a4745479fc1e8cfd2bdb74e.jpg]: https://img-blog.csdnimg.cn/ceaefc422a4745479fc1e8cfd2bdb74e.jpg