前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Implement strStr()/KMP算法

[Leetcode][python]Implement strStr()/KMP算法

作者头像
蛮三刀酱
发布2019-03-26 16:46:27
6750
发布2019-03-26 16:46:27
举报
文章被收录于专栏:蛮三刀的后端开发专栏

题目大意

字符串匹配

解题思路

两种思路: 1. 直接一个个匹配过去(遍历) 2. KMP算法:参考 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html http://blog.csdn.net/coder_orz/article/details/51708389

代码

遍历

代码语言:javascript
复制
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        length = len(needle)
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

KMP

最后两个测试集超时,将就了,KMP算法的实现还是很重要的。

代码语言:javascript
复制
class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not haystack:
            if needle:
                return -1
            else:
                return 0
        if not needle:
            return 0
        return self.kmp_match(haystack, needle)

    #KMP
    def kmp_match(self, s, p):  
        m = len(s)
        n = len(p)  
        cur = 0  # 起始指针cur  
        table = self.partial_table(p)  
        # print(table)
        while cur <= m-n: # 长度不够就终止  
            # print("新一轮匹配,开始位置", cur)
            for i in range(n):  # 一次匹配长度  
                if s[i+cur] != p[i]:  
                    # print(s[i+cur], p[i], '不匹配。查表位置:', i, i - table[i-1])
                    cur += max(i - table[i-1], 1) # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位  
                    break  
            else:
                return cur 
        return -1  

    #部分匹配表  
    def partial_table(self, p):  
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''  
        prefix = set()  
        table = [0]  
        for i in range(1, len(p)):  # 从1开始进行前后缀比较  
            prefix.add(p[:i])  # 前缀每次累加就行
            postfix = set()
            for j in range(1, i+1):  # i+1 因为i需要包括
                postfix.add(p[j:i+1]) 
            # print(prefix, postfix)
            # print(prefix&postfix, len(prefix&postfix))
            # table.append(len((sorted((prefix&postfix),key = len)or {''}).pop()))
            if prefix&postfix:
                table.append(max(map(len,prefix&postfix)))
            else:
                table.append(0)
        return table  

总结

题目标签是双指针,我觉得基本思路就是找到第一个字母后逐一匹配后面的,其实KMP也是这样的,只不过用了一个表直接利用之前的匹配信息跳过一些不必要的匹配,有空仔细研究下。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年08月28日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
    • 遍历
      • KMP
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档