# 594.strStr II

## 1.Description(Hard)

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*m\_and the length of the source string is n*.\
If target does not exist in source, just return -1.

**Example**

Given source =`abcdef`, target =`bcd`, return`1`.

[**Tags**](https://www.lintcode.com/en/problem/strstr-ii/#tags)

[Hash Table](https://www.lintcode.com/tag/hash-table/)

## 2.Code

O(n + m)的算法有2个: KMP和Rabin-Karp。

KMP有个问题，因为DFA的方法预处理的表的空间为R \* M，所以memory会越界。

<http://wiki.jikexueyuan.com/project/kmp-algorithm/define.html>

还有一个best performance是O(N/M)但是worst case是O(MN)的算法Boyer-Moore。

<https://xuezhashuati.blogspot.ca/2017/03/lintcode-594-strstr-ii.html>

```
public int strStr2(String source, String target) {
        // Write your code here
        if (source == null || target == null) {
            return -1;
        }

        int N = source.length();
        int M = target.length();

        if (M == 0) {
            return 0;
        }

        int R = 31;
        int Q = 997;
        int RM = 1;

        for (int i = 0; i < M; i++) {
            RM = RM * R % Q;
        }

        int targetHash = 0;
        for (int i = 0; i < M; i++) {
            targetHash = (targetHash * R + target.charAt(i)) % Q;
        }

        int sourceHash = 0;
        for (int i = 0; i < N; i++) {
            sourceHash = (sourceHash * R + source.charAt(i)) % Q;
            if (i < M - 1) {
                continue;
            }

            if (i >= M) {
                sourceHash = sourceHash - (source.charAt(i - M) * RM) % Q;
                if (sourceHash < 0) {
                    sourceHash += Q;
                }
            }

            if (sourceHash == targetHash) {
                if (source.substring(i - M + 1, i + 1).equals(target)) {
                    return i - M + 1;
                }
            }
        }

        return -1;
    }
```