Java实现字符串匹配RK(RabinKarp)算法

川长思鸟来 2021-12-15 21:55 279阅读 0赞

#### 前言 ####

写这篇博客主要是因为在看了相关的RK算法原理之后，发现算法都是用C语言实现的。对于习惯使用Java的我来说有点不习惯。所以这里写了一个Java语言版本的实现。

这篇文章不会讲解RK算法的原理，只是Java版本的实现。具体的算法参考了[这篇博客][Link 1] 。博客里也详细讲解了RK的原理。

/**
     * 字符串匹配RK算法，BF算法的升级版本
     * Created by LinGer on 2019/7/3
     */
    public class RabinKarp {
        
    
        /**
         * 假设只匹配字母，所以d等于26
         * @param str 主串
         * @param pattern 模式串
         * @return
         */
        public static int rabinKarp(String str, String pattern){
        
            int size1 = str.length();
            int size2 = pattern.length();
    
            //哈希时需要用到进制计算，这里只涉及26个字母所以使用26进制
            int d = 26;
            //防止hash之后的值超出int范围，对最后的hash值取模
            //q取随机素数，满足q*d < INT_MAX即可
            int q = 144451;
    
            //str子串的hash值
            int strCode = str.charAt(0) - 'a';
            //pattern的hash值
            int patternCode = pattern.charAt(0) - 'a';
            //d的size2-1次幂，hash计算时，公式中会用到
            int h = 1;
    
            //计算sCode、pCode、h
            for (int i = 1; i < size2; i++) {
        
                patternCode = (d*patternCode + pattern.charAt(i)-'a') % q;
                //计算str第一个子串的hash
                strCode = (d*strCode + str.charAt(i)-'a') % q;
                h = (h*d) % q;
            }
    
            //最大需要匹配的次数
            int frequency = size1 - size2 + 1;
            //字符串开始匹配，对patternCode和strCode开始比较，并更新strCode的值
            for (int i = 0; i < frequency; i++) {
        
                if(strCode == patternCode && ensureMatching(i, str, pattern)){
        
                    return i;
                }
                //更新strCode的值，即计算str[i+1,i+m-1]子串的hashCode
                strCode = ((strCode - h*(str.charAt(i)-'a'))*d + str.charAt(i+size2) - 'a');
            }
            return -1;
        }
    
        /**
         * hash值一样并不能完全确保字符串一致，所以还需要进一步确认
         * @param i hash值相同时字符串比对的位置
         * @param pattern 模式串
         * @return
         */
        private static boolean ensureMatching(int i, String str, String pattern) {
        
            String strSub = str.substring(i, i+pattern.length());
            return strSub.equals(pattern);
        }
    
        public static void main(String[] args) {
        
            String str = "abcabcabc";
            String pattern = "cabc";
            System.out.println("第一次出现的位置:" + rabinKarp(str, pattern));
        }
    }

[Link 1]: https://blog.csdn.net/jjwwwww/article/details/81676479