Implement strStr()

• Lintcode : 13 / Leetcode : 28
• Level : Easy

Problem

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

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

Example
Example 1:

Input: source = "source" ，target = "target"
Output: -1    
Explanation: If the source does not contain the target content, return - 1.
Example 2:

Input:source = "abcdabcdefg" ，target = "bcd"
Output: 1    
Explanation: If the source contains the target content, return the location where the target first appeared in the source.
Challenge
O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Clarification
Do I need to implement KMP Algorithm in a real interview?

Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure you confirm with the interviewer first.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

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

Answer

class Solution {
public:
    int strStr(string &source, string &target) {
        int s = source.size(), t = target.size();
        if (t == 0) return 0;
        const int BASE = 100007;
        const int seed = 37;
        long long sourceHashCode = 0;
        long long targetHashCode = 0;
        for (int i = 0; i < t; i++) {
            targetHashCode = (targetHashCode * seed + target[i]) % BASE;
        }
        long long power = 1;
        for (int i = 0; i < t; i++)
            power = power * seed % BASE;

        for (int i = 0; i < s; i++) {
            sourceHashCode = (sourceHashCode * seed + source[i]) % BASE;
            if (i < t - 1) continue;
            if (i >= t) {
                sourceHashCode = sourceHashCode - power * source[i - t] % BASE;
                if (sourceHashCode < 0) sourceHashCode += BASE;
                sourceHashCode = sourceHashCode % BASE;
            }
            if (sourceHashCode == targetHashCode && source.substr(i - t + 1, t) == target) {
                return i - t + 1;
            }
        }
        return -1;
    }
};

tags: string

​