文档章节

字符串匹配

w
 wolfoxliu
发布于 2017/04/20 19:43
字数 373
阅读 17
收藏 0

部分转载自

http://lib.csdn.net/article/python/39140#focustext 和

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

s -- 目标串        p -- 模式串

# 朴素字符串匹配算法,时间复杂度为O(m*n)
def naive_match(s, p):
    m, n = len(p), len(s)
    for i in range(n-m+1):      # 一共比较n-m+1次
        if s[i:i+m] == p:
            return i
    return -1

print naive_match('abc', 'bc')
print naive_match('ABCDABCDABDE', 'ABCDABD')


# 匹配表
def partial_table(p):
    m = len(p)
    tab = [0] * m
    prefix = set()
    for i in range(1, m):
        prefix.add(p[:i])
        suffix = {p[j:i+1]for j in range(1, i+1)}
        tab[i] = max(map(lambda x: len(x), (prefix & suffix or {''})))
    return tab


# KMP算法, 时间复杂度为O(m+n)
def kmp_match(s, p):

    table = partial_table(p)

    m, n = len(p), len(s)
    for i in range(n-m+1):         # 最多的可能比较n-m+1
        for j in range(m):
            if s[i+j] != p[j]:
                i += max(j - table[j-1], 1)
                break
        else:
            return i
    return -1

print kmp_match('abc', 'bc')
print kmp_match('ABCDABCDABDE', 'ABCDABD')

KMP算法运用场景:用于模式串匹配较多的情况下。

KMP算法的缺点:当目标串很大且匹配很罕见的时候(比如在文章中找单词或在邮件里找垃圾过滤关键字)

 

对于目标串很大且匹配很罕见的情况,使用Boyer-Moore算法效率比较高。

Boyer-Moore算法请见:

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

 

对于子字符串的查找,Python提供了find()和index()两个函数,这两个函数实现的算法是Horspool算法,Horspool算法可以看做是简化版的Boyer-Moore算法。

请见:http://blog.csdn.net/jjdiaries/article/details/12771439

 

© 著作权归作者所有

共有 人打赏支持
w
粉丝 8
博文 13
码字总数 10108
作品 0
杭州
程序员
私信 提问

暂无文章

租房软件隐私保护如同虚设

近日,苏州市民赵先生向江苏新闻广播新闻热线025-84658888反映,他在“安居客”手机应用软件上浏览二手房信息,并且使用该软件自动生成的虚拟号码向当地一家中介公司进行咨询。可电话刚挂不久...

linux-tao
今天
1
0
分布式项目(五)iot-pgsql

书接上回,在Mapping server中,我们已经把数据都整理好了,现在利用postgresql存储历史数据。 iot-pgsql 构建iot-pgsql模块,这里我们写数据库为了性能考虑不在使用mybatis,换成spring jd...

lelinked
今天
4
0
一文分析java基础面试题中易出错考点

前言 这篇文章主要针对的是笔试题中出现的通过查看代码执行结果选择正确答案题材。 正式进入题目内容: 1、(单选题)下面代码的输出结果是什么? public class Base { private Strin...

一看就喷亏的小猿
今天
2
0
cocoapods 用法

cocoapods install pod install 更新本地已经install的仓库 更新所有的仓库 pod update --verbose --no-repo-update 更新制定的仓库 pod update ** --verbose --no-repo-update...

HOrange
今天
3
0
linux下socket编程实现一个服务器连接多个客户端

使用socekt通信一般步骤 1)服务器端:socker()建立套接字,绑定(bind)并监听(listen),用accept()等待客户端连接。 2)客户端:socker()建立套接字,连接(connect)服务器,连接上后...

shzwork
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部