594.strStr II

1.Description(Hard)

ImplementstrStrfunction in O(n + m) time.

strStrreturn the first index of the target string in a source string. The length of the target string ism_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, return1.

Tags

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;
    }