算法面试真题详解：字符串查找 II

描述
实现时间复杂度为 O(n + m)的方法 strStr。
strStr 返回目标字符串在源字符串中第一次出现的第一个字符的位置. 目标字串的长度为 m , 源字串的长度为 n . 如果目标字串不在源字串中则返回 -1。

在线评测地址：领扣题库官网
样例1
输入：source = "abcdef"， target = "bcd"
输出：1
解释：
字符串第一次出现的位置为1。

样例2
输入：source = "abcde"， target = "e"
输出：4
解释：
字符串第一次出现的位置为4。

算法：HASH

• 字符串Hash可以通俗的理解为，把一个字符串转换为一个整数。
• 如果我们通过某种方法，将字符串转换为一个整数，就可以快速的判断两个字符串是否相同。
• 当然如果有不同的两个字符串同时Hash到一个整数，这样就比较麻烦了，所以我们希望构造这个Hash函数使得他们成为一个单射。
  算法思路
• 给定一个字符串S,对于一个字符c我们规定id(c)=c-'a'+1
• hash[i]=(hash[i-1]*p+id(s[i]))%MOD
• p和MOD均为质数，并且要尽量大
  代码思路
  1. 计算target的hash值
  2. 计算source的hash值的过程中，依次计算每targetLen位的hash值。

     假设target长度为2，source为“abcd”

     hash("cd") = (hash("bc + d") - hash("b")*2 ) % BASE
     复杂度分析
     N表示字符串source长度，M表示字符串target长度

• 空间复杂度：O(1)
• 时间复杂度：O(N+M)

public class Solution {

private static final Integer BASE = 100007;

/*

 * @param source: A source string

 * @param target: A target string

 * @return: An integer as index

 */

public int strStr2(String source, String target) {

    if (source == null || target == null) {

        return -1;

    }

    int m = target.length();

    if (m == 0) {

        return 0;

    }

    int power = 1;

    for (int i = 0; i < m; i++) {

        power = (power * 31) % BASE;

    }

    //先计算一下target的hash值

    int targetCode = 0;

    for (int i = 0; i < m; i++) {

        targetCode = (targetCode * 31 + target.charAt(i)) % BASE;

    }

    //当source code 加上右边一个character，就要减掉左边的一个character

    int sourceCode = 0;

    for (int i = 0; i < source.length(); i++) {

        sourceCode = (sourceCode * 31 + source.charAt(i)) % BASE;

        if (i <= m - 1) {

            continue;

        }

        sourceCode = (sourceCode - power * source.charAt(i - m)) % BASE;

        if (sourceCode < 0) {

            sourceCode += BASE;

        }

        //若hash值相同，返回答案

        if (sourceCode == targetCode) {

            return i - m + 1;

        }

    }

    return -1;

}

}
更多题解参考：九章官网solution