【面试刷题】字符串匹配Robin Karp算法

【面试刷题】字符串匹配Robin Karp算法

一、题目LeetCode-28.实现strStr()

【面试刷题】字符串匹配Robin Karp算法

【面试刷题】字符串匹配Robin Karp算法

二、实现O(n^2)的普通算法

class Solution {
    public int strStr(String haystack, String needle) {
        //进行异常判断
        if (haystack==null||needle==null)
            return 0;
        
        for (int i = 0; i<haystack.length() - needle.length() + 1;i++){
            int flag = 1;
            for (int j = i; j<i+needle.length(); j++){
                if (haystack.charAt(j) != needle.charAt(j-i)){
                    flag = 0;
                    break;
                }  
            }
            if (flag == 1)
                return i;
        }

        return -1;
    }
}

三、Robin Karp算法

在字符串比较的时候,需要向上面的普通方法,一个一个字母去匹配比较。

在数字比较的时候,只需要比较数字的值即可。

那么,如何把字符串的比较变为数字的比较呢?----hashCode

1、编写HashFunction()基础

可以通过字符,和一个数的乘积来转换为一个数字

【面试刷题】字符串匹配Robin Karp算法

比如abcd,拆分成a、b、c、d四个char类型,然后分别乘以对于的底数最后相加,就是这个字符串的Hash值。

有可能会超出整数的范围,那么可以对出来的值取模。

例:
"abcde"
= (a * 31^4 ) + (b * 31^3 ) + (c * 31^2 ) + (d * 31^1 ) + (e * 31^0 ) % 10^6

在此基础之上,如果要得到"bcde"的hash值怎么办?
模运算,用"abcde"的hash值 减去 (a * 31^4 )得到的值,再次模10^6即可

如果计算出来的hash值相同,那么可能两个字符串是相同的,还需要进一步判断。

如果计算出来的hash值不相同,那么两个字符串一定是不相同的。

效率取决于会有多少hash冲突。整个的时间复杂度是O(n + m)次,最后的匹配是m次。

2、实现Robin Karp算法

class Solution {
    public int BASE = 1000000;
    public int strStr(String source, String target) {
        if (source == null || target == null){
            return 0;
        }
        
        int m = target.length()
        if (m.length() == 0){
            return 0;
        }
        
        // 31 ^ m
        int power = 1;
        for (int i = 0; i < m; i++){
            power = (power * 31) % BASE;
        }
        
        //计算targetCode
        int targetCode = 0;
        for (int i = 0; i < m; i++){
            targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
        }
        
        int hashCode = 0;
        for (int i = 0; i < source.length(); i++){
            //abc + d
            hashCode = (hashCode * 31 + source.charAt(i)) % BASE;
            //所计算的hashCode字符串长度小于目标的长度
            if (i < m-1){
                continue;
            }
            
            //abcd - a,所计算的hashCode字符串大于等于目标的长度,如i=2,m=2实际上已经计算了三个字符。
            if (i >= m){
                //减掉第一个字符后的hashCode,例如source.charAt(2 - 2)
                hashCode = hashCode - (source.charAt(i - m) * power)%BASE;
                if (hashCode < 0){//变为整数
                    hashCode += BASE;
                }
            }
            
            //double check the String
            if (hashCode == targetCode){
                //注意此时的substring,在Java中是不包含最后一个的。边界处理的问题,左闭右开。
                if (source.substring(i - m + 1, i + 1).equals(target)) {
                    return i - m + 1;
                }
            }
        }
        return -1;
    }
}
上一篇:JavaWeb学习day6-Response初学


下一篇:SpringMVC文件上传及下载