字符串匹配就是给定两个字符串 T 和 P, 看T是否完全包含P。 比如 T = abcdeff, P = abce,则P不匹配T,如果P = eff,则P匹配T。
非常原始的做法就是从T的第一个字母开始和P进行比较,如果达到P的最后一个字母仍旧是相同的,那么就成立,否则,从T的第二个字母有开始比较;直到T的最后一个字母。这种做法复杂度为O(nm). n 是T的长度, m是P的长度。
本文文章介绍KMP算法,它的复杂度为 O(n).
KMP算法的原理是从两个字符串的第一个字母开始比较,如果遇到字母不匹配,我们保持T字符串的下标不改变,而是把P字符串的下标移到一个“合适”的位置,然后一直这样操作,直到T字符串遍历完毕。
那么,当不匹配产生时,如何才能找到P字符串的“合适”的位置呢?所谓合适,是指有一个最大值 j 使得 P[1..j]=T[i-j+1..i].我们用X[m] 来保存应该回到的位置 j, 而这里的 i 是指 “指针” 指到的T字符串的当前运行位置。以下程序生成X[m]:
有了X[m], 当我们遇到不匹配的时候,对于P字符串,我们就不用再从开始做起,而是退回到一个“合适”的位置,而对于T字符串,根本就不用回退。所以,这个算法是:
现在我们再对它的复杂度进行分析。 这里的分析利用了 amortized analysis. 具体如下:
在整个for 循环里,一共执行了n次,由于 第一个while 语句 和第一个 if语句是不可同时成立的,而每一次执行while语句,都会使得q变小。而q最大不可能超过n。也就是是说,在整个for循环里,while里的语句最多执行了n次,所以每一次for循环,while里的语句最多执行了1次。
参考:
http://www.matrix67.com/blog/archives/115/
分享到:
相关推荐
介绍字符串匹配算法的书,包括经典的B-M, KMP算法,并包含C代码的实现
一种基于匹配区域特征的相似字符串匹配过滤算法,孙德才,孙星明,为加快相似字符串匹配中过滤算法的匹配速度,提出了一种基于匹配区域特征的过滤算法。该算法对文本串预处理采用了q-gram索引结构;
一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有...
stringMatching Java中的一些字符串匹配算法:算法:天真的搜索,Knuth Morris Pratt和Boyer-Moore 随时修改此软件:)
通配符字符串匹配字符串匹配,其中一个字符串包含通配符( )
数据结构中的字符串的朴素匹配(简单匹配)算法
字符串匹配算法字符串匹配算法
基于有限自动机进行字符串匹配。有详细算法描述。
字符串匹配 使用位置树在2D&3D空间中进行字符串匹配。
串匹配(String Matching)问题是计算机科学中的一个基本问题, 也是复杂性理论中研究的最广泛的问题之一. 分析几种常用的模式匹配算法, 提出一种基于KMP的改进算法IKMP(Improved-KMP)算法. 该算法以KMP为基础, 引入好...
Hadoop 中的超长字符串匹配 Hadoop 中的超长字符串匹配。 给定一个没有 '\n' 或任何仅包含 4 个字符的分隔符的超长字符串,包括多个 1 GB 文件中的 a、b、c 和 d。 目标是使用 Hadoop 在多个 1 GB 文件中找到给定...
介绍确定字符串匹配算法,对于生物信息学爱好者很有用
字符串匹配问题的目的是找到单词中所有出现的单词。 天真的算法 使用两个嵌套循环搜索文本。 外循环遍历所有可能的位置,而内循环遍历文本和当前位置中单词的相应字符,同时比较相应的字符。 如果发生不匹配,则内部...
(大一计算机新生作业)带通配符的字符串匹配 输入两个字符串(不包含空格)用空格分开,前一个字符串中含有通配符‘*’和‘?’,其中‘*’可代替任意长度的字符串,'?'可代替任一字符,若前者与后者匹配,输出...
Python 中的字符串匹配 问题 我经常发现自己需要让用户输入一个字符串并从字符串列表中找到该字符串的最佳匹配项。 为了弥补拼写错误,我发现非常有用。 但是速度呢? 超过 100,000 个单词的速度很慢。 解决方案 ...
字符串匹配操作。输入主串和子串,通过匹配算法,统计匹配次数。
参数化字符串匹配实现软件剽窃检查 软件抄袭检查的参数化字符串匹配实现
尽管数据加密提供了足够的保护,但要对加密数据支持丰富的查询功能(例如字符串匹配)是一项挑战。 在这项工作中,我们提出了第一个基于对称密钥的方法来支持云计算中的隐私保护字符串匹配。 我们描述了一种高效且...
PolyFuzz执行模糊字符串匹配,字符串分组,并包含广泛的评估功能。 PolyFuzz旨在将模糊字符串匹配技术整合到一个框架中。 当前,方法包括各种编辑距离度量,基于字符的n-gram TF-IDF,词嵌入技术(例如FastText和...
字符串匹配是计算机科学中的一个基本问题。 它在搜索引擎,病毒检测,序列比对和许多其他应用中起着重要作用。 Aho-Corasick(AC)算法是一种广泛使用的多字符串匹配算法。 在本文中,我们提出了一种基于节点分组的...