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

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

Have you met this question in a real interview?

Yes

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.

Example

If source ="source"and target ="target", return-1.

If source ="abcdabcdefg"and target ="bcd", return1.

Robin-Karp

用 a * 31 ^ 4 + b * 31 ^ 3 + c * 31 ^ 2 + d * 31 ^1 + e * 31 ^ 0 来表示 abcde

from itertools import izip
class Solution:
    """
    @param: source: source string to be scanned.
    @param: target: target string containing the sequence of characters to match
    @return: a index to the first occurrence of target in source, or -1  if target is not part of source.
    """

    def strStr(self, source, target):
        HASH_BASE = 1000000
        # write your code here
        if source == None or target == None:
            return -1

        if len(target) == 0:
            return 0

        s = len(source)
        t = len(target)

        #get the exponential based on the target length
        #get the hashcode for the target
        power = 1
        tar_hash = 0
        for char in target:
            power = (power * 31) % HASH_BASE
            tar_hash = (tar_hash * 31 + ord(char)) % HASH_BASE

        source_hash = 0
        for i, char in enumerate(source):
            source_hash = (source_hash * 31 + ord(char)) % HASH_BASE
            if i < t - 1:
                continue

            if i >= t:
                source_hash = source_hash - (ord(source[i - t]) * power % HASH_BASE)
                if source_hash < 0:
                    source_hash += HASH_BASE

            if source_hash == tar_hash:
                is_same = True
                for s_char, t_char in izip(source[(i-t+1):(i+1)], target):
                    if s_char != t_char:
                        is_same = False
                        break
                if is_same:
                    return i - t + 1

        return -1