strStr II

• Lintcode : 594 / Leetcode :
• Level : Hard

Problem

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
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.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(m + n)
space: O(1)

Answer

class Solution {
public:
    int strStr2(const char* source, const char* target) {
        if (source == nullptr || target == nullptr) return -1;
        int s = 0, t = 0;
        while (source[s]) s++; // strlen(source)
        while (target[t]) t++; // strlen(target)
        if (t == 0) return 0;
        if (s == 0) return -1;

        const int BASE = 1000007;
        const int seed = 37;
        long long targetHash = 0, sourceHash = 0, power = 1;
        for (int i = 0; i < t; i++) {
            targetHash = (targetHash * seed + target[i]) % BASE;
        }
        for (int i = 0; i < t; i++) {
            power = power * seed % BASE;
        }
        for (int i = 0; i < s; i++) {
            sourceHash = (sourceHash * seed + source[i]) % BASE;
            if (i < t - 1) continue;
            if (i >= t) {
                sourceHash = sourceHash - power * source[i - t] % BASE;
                if (sourceHash < 0) sourceHash += BASE;
            }
            if (sourceHash == targetHash && isSame(source, target, i - t + 1, t)) {
                return i - t + 1;
            }
        }
        return -1;
    }
    bool isSame(const char * source, const char * target, int index, int t) {
        for (int i = 0; i < t; i++) {
            if (source[index + i] != target[i]) return false;
        }
        return true;
    }
};

tags: string

​