594. strStr II

Description

Implement strStr function in O(n + m) time.

strStr return the first index of the target string in a source string. The length of the target string is mand the length of the source string is n.

If target does not exist in source, just return -1.

Have you met this question in a real interview?Yes

Problem Correction

Example

Example 1:

Input：source = "abcdef"， target = "bcd"

Output：1

Explanation：

The position of the first occurrence of a string is 1.

Example 2:

Input：source = "abcde"， target = "e"

Output：4

Explanation：

The position of the first occurrence of a string is 4.

思路：

在解决 strstr 这个问题时，KMP 算法学起来比价费劲，不好理解，且对于其他的算法面试问题没有什么帮助。这里推荐大家学习一个替代品 ——

Rabin Karp Algorithm。这个算法同样可以达到 O(n + m) 的线性时间复杂度，而且其利用到的哈希函数基本实现原理是必须掌握的面试算法知识点。

哈希函数：

base 可以是任何数，但是取太小的话重复值会太高， 31也可以调整， 对于负的结果需要加base使其为正数。

abc = (a*31**2 + b* 31**1 + c*31**0)%base

abcd =(abc*31 + d)% base

bcd = abcd - a*31**3%base

运用此算法将target和source从str转换成了int，减少了遍历时间，从而降低了复杂度。

还需要注意字符串“”与None的区别。

同时哈希值相等不代表原值也相等，需要二次验证。

代码：