字符串查找

LintCode题目地址

def strStr(self, source, target):
        # write your code here
        if source == None or target == None:
            return -1
        n = len(source)
        m = len(target)
        if (n == 0 and m == 0) or m == 0:
            return 0
        if n == 0 or n < m:
            return -1
        i, j = 0, 0
        while i < n - m + 1:
            while j < m:
                if source[i+j] == target[j]:
                    if j == m-1:
                        return i
                    else:
                        j += 1
                        
                else:
                    i = i+1 #i只能一步步向后移动
                    j = 0
                    break
        return -1

KMP其实只改进了i的移动速度，不是一步步向后，可能是多步

    #生成next表
    def partial_table(self, p):  
     
        prefix = set()  #前缀
        postfix = set()   #后缀
        ret = [0]  
        for i in range(1,len(p)):  
            prefix.add(p[:i])  
            postfix = {p[j:i+1] for j in range(1,i+1)}  
            # 前缀后缀最长公共元素长度
            ret.append(len((prefix&postfix or {''}).pop()))  
        return ret
    
    def strStr(self, source, target):
        # 边界条件判断
        if source == None or target == None:
            return -1
        n = len(source)
        m = len(target)
        if (n == 0 and m == 0) or m == 0:
            return 0
        if n == 0 or n < m:
            return -1
        #初始化next表    
        nextList = self.partial_table(target)
        i, j = 0, 0
        
        #开始循环
        while i < n - m + 1:
            while j < m:
                if source[i+j] == target[j]:
                    if j == m-1:
                        return i
                    else:
                        j += 1
                        
                else:
                    if (j - nextList[j - 1]) + i > n - m:
                        break
                    #核心差距在这里，其他代码一致
                    i = max((j - nextList[j - 1]), 1)  + i #i多步向后移动，唯一和第一个程序不一样的地方
                    j = 0
                    break
        return -1