【必备算法】字符串（匹配问题）：1.暴力匹配，2.Rabin-Karp，3.KMP

古城微笑少年丶 2022-12-15 12:54 121阅读 0赞

## 1.暴力匹配 ##

暴力匹配即列出所有子串进行比较

public int forceSearch(String txt, String pat) {
        
    	// 遍历内容串txt，选取起点
        for (int i = 0, j = 0; i < txt.length(); i++) {
        
        	// 从起点开始与模式串pat对比
            for (j = 0; j < pat.length(); j++) 
                if (pat.charAt(j) != txt.charAt(j)) break;
            if (j == pat.length()) return i;
        }
        return -1;
    }

## 2.Rabin-Karp ##

暴力优化，枚举所有子串，但不用所有子串都比较（Hash相同再比对）

public static final int D = 256;
    public static final int Q = 9997;
    
    public int RabinKarpSearch(String txt, String pat) {
        
        int M = pat.length(), N = txt.length();
        int patHash = 0, int txtHash = 0;
        // 1.计算txt初始Hash，pat的Hash
        // 注：Hash算法的设计很重要，要尽量避免重复；这里的Hash算法类似二进制转十进制，加权相加
        for (int i = 0; i < M; i++) {
        
            // 每循环一次就 * D 相当于加权了（取模时防止过大）, pow (256, i) + char(i)
            patHash = (D * patHash + pat.charAt(i)) % Q;
            txtHash = (D * txtHash + txt.charAt(i)) % Q;
        }
        
        // 2.计算最高位权值（左边开始第一位，i）
        // 注：后面要的改变子串相当于将最高位删除，然后加上一个最低位
        int highestPow = 1;
        for (int i = 0; i < M - 1; i++) {
        
            highestPow = (highestPow * D) % Q;
        }
        
        // 3.列举所有子串，只有Hash值相同的才进行比对；否则更新txtHash进行下一轮
        for (int i = 0, j = 0; i <= N - M; i++) {
        
            // 3.1 当前子串Hash与patHash相等，可以进行比对（核心！！！）
            if (patHash == txtHash) {
        
                for (j = 0; j < M; j++) 
                   if (txt.charAt(j) != pat.charAt(j)) break;
                if (j == M) return i;
            }
            // 3.2 Hash不相等或匹配失败，更新txtHash
            // 注：1.这里不能用else
            //     2.txtHash = （txtHash - 最高位 + 新的最低位）% Q
            // 				 = （txtHash - (char(i)*highestPow) + char(i+M)) % Q
            //     3.若txtHash < 0，直接加上Q就行（Q取模得到的）
            txtHash = (D * (txtHash - txt.charAt(i) * highestPow) + txt.charAt(i + M)) % Q;
            if (txtHash < 0) txtHash += Q;
    	}
        
        return -1;
    }

## 3.KMP ##

暴力优化，不枚举所有子串

*  子串们的最长相同前后缀表 ----右移补-1-----> next表
 *  碰到不匹配的位置，就根据当前位置在next表中的值k，将目标串的k位置移到不匹配位置

[参考视频][Link 1]，[参考1][1]，[参考2][2]

public class KMP {
        
    
        /**
         * 求KMP算法的next数组
         * @param pattern 需要进行匹配的模式子串
         * @return KMP算法的next数组
         */
        public static int[] getNext(String pattern) {
        
            // 因为next数组下标是从1开始的，所以数组长度为字符串长度+1
            int[] next = new int[pattern.length() + 1];
           
            // 数组前两个数字有默认值
            next[0] = 0;
            next[1] = 1;
           
            // 从第二个字符开始计算next数组
            for (int i = 2; i <= pattern.length(); i++) {
        
               
                // 获取模式串前缀子串
                String subStr = pattern.substring(0, i);
                // 前缀子串的相同前后缀的最大长度
                int max = 0;
    
                // 求前缀子串的相同前后缀的最大长度
                for (int j = 1; j < i; j++) {
        
                    // 获得长度为j的前缀子串的前缀
                    String prefix = subStr.substring(0, j);
                    //获 得长度为j的前缀子串的后缀
                    String suffix = subStr.substring(subStr.length() - j);
                   
                    //如果前缀子串的前后缀相等（长度为j）
                    if (prefix.equals(suffix)) {
         
                        // 更新前缀子串的相同前后缀的最大长度
                        // 这个肯定会越来越大的，j会不断++，最后求出最大长度
                        max = j;
                    }
                }
               
                // 将求得的模式串的前缀的最大前后缀长度，写入对应下标的next数组
                next[i] = max;
            }
            // 返回求得的next数组
            return next;
        }
    
        /**
         * KMP算法的字符串匹配算法
         * @param content 内容串
         * @param pattern 模式串
         * @return 模式串在内容串的索引，跟String类的indexOf()方法的返回值一样，如果未找到返回-1
         */
        public static int match(String content, String pattern) {
        
            // 如果模式串比内容串还要长
            if (pattern.length() > content.length()) {
        
                return -1;
            }
           
            // 获取模式串的next数组
            int[] next = getNext(pattern);
           
            // 内容串ci指针和模式串pi指针向前遍历
            for (int ci = 0; ci < content.length(); ci++) {
        
                for (int pi = 0; pi < pattern.length(); pi++) {
        
                    // 如果内容串已经越界了
                    if (ci >= content.length()) {
        
                        // 超出范围还没找到，返回-1
                        return -1;
                    }
                   
                    // 当前内容串的比较字符
                    char charC = content.charAt(ci);
                    // 当前模式串的比较字符
                    char charP = pattern.charAt(pi);
                   
                    // 如果两个字符相等
                    if (charC == charP) {
        
                        // 如果匹配到了模式串最后一个字符
                        if (pi == pattern.length() - 1) {
        
                            // 返回索引
                            return ci - pi;
                        // 如果还没到模式串最后一个字符
                        } else {
        
                            // 内容串右移一位
                            ci++;
                        }
                    // 如果两个字符不相等
                    } else {
        
                        // 找到内容串需要右移的位数
                        int contentRightOffset = pi - next[pi];
                        // 找到内容串的下一个起始坐标
                        int restart = ci - pi + 1 + contentRightOffset
                        // 注意，这里需要-1，应对for循环里面的自增
                        ci = restart - 1;
                       
                        // 跳出当前模式串的for循环，重新匹配模式串
                        break;
                    }
                }
            }
            // 找完了还没有找到，返回-1
            return -1;
        }
    
        /**
         * 测试KMP算法
         * @param args
         */
        public static void main(String[] args) {
        
            // 测试内容串
            String content = "abaabaabbabaaabaabbabaab";
           
            // 测试模式串
            String pattern = "abaabbabaab";
           
            // 输出模式串在内容串的索引号
            System.out.println(match(content, pattern));
        } 
    }

[Link 1]: https://www.bilibili.com/video/av11866460?from=search&seid=17425875345653862171
[1]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[2]: https://wiki.jikexueyuan.com/project/kmp-algorithm/define.html