Rabin Karp算法寻找目标字符串在原字符串中的位置

前言

注：本文主要作为自己学习的记录，并没有详细介绍算法的每一步骤，如有问题欢迎讨论。

要解决的问题如下例：
在"abcde" 中寻找"bcd"，则返回位置：1。

一、使用rabin karp算法寻找目标字符串在原字符串中的位置。

代码如下：在这里插入代码片

public int targetIndex(String source, String target) {
    if (source == null || target ==null || source.equals("") || target.equals(""))
        return -1;

    final int BASE = 1000000;
    int tL = target.length();
    // 31^tL； power的作用是用于减去原先第一个数，例如： abcd - a；
    // 为什么不是31^(tL-1)呢，因为bcd最高次数为31^(tL-1)，因此被减去的a的位数只能是31^(tL-1)
    int power = 1;
    for (int i = 0; i < tL; i++) {
        power = (power * 31) % BASE;
    }

    int targetCode = 0;
    for (int i = 0; i < tL; i++) {
        targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
    }
    /*
    for (int i = 0; i < source.length(); i++) {
        if (i > source.length() - tL)
            break;

        int hashCode = 0;
        for (int j = 0; j < tL; j++) {
            hashCode = (hashCode * 31 + source.charAt(i + j)) % BASE;
        }

        if (hashCode != targetCode)
            continue;
        else if (source.substring(i, i+tL).equals(target)) {
            return i;
        }
    }
        */
    int hashCode = 0;
    for (int i = 0; i < source.length(); i++) {
        hashCode = (hashCode * 31 + source.charAt(i)) % BASE;
        if (i < tL)
            continue;
        if (i >= tL) {
            hashCode = hashCode - (source.charAt(i - tL) * power) % BASE;
            // 等式右边的第一个hashCode在上步骤中已经%BASE了，因此只用让减号后面的式子%BASE
            if (hashCode < 0) {
                hashCode += BASE;
            }
        }

        if (hashCode != targetCode)
            continue;
        else if(source.substring(i-tL+1, i+1).equals(target))
            //无法确定是(i-tL+1)还是(i-tL)还是(i-tL-1)，带入一个极端数就可以了，例如 假设i=2，tL=3那么起始位置应该是0，即i-tL+1
            return i-tL+1;
    }

    return -1;
}

（调了半天格式也没调对，暂时放弃了，-_-#）
若采用被注释的部分，实际时间复杂度为O(n*m)跟逐个比较一样，使用非注释部分，则时间复杂度为O(n)。

总结

1.Rabin Karp算法的思想是将字符串转换成一个尽量唯一的hash值，避免逐个比较两个字符串中的每个字符，从而降低时间复杂度。
2.之所以说尽量的原因是，使用a*(31^tL-1) + …的方式仍然有可能照成hash值重复。
3.为什么BASE是10^6，留下一个疑问，和大家一起探讨。