AC自动机算法
在计算机科学中，艾侯-科拉希克算法（）是由阿尔佛雷德·艾侯和玛格丽特·J·科拉希克（Margaret J. Corasick）发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa…
标签：#字符串匹配算法
共 7 篇文章
KMP算法
:在本文中，将使用始于零的数组来表示字符串。比如，若字符串S = "ABC"，则S[2]表示字符'C'。这种表示方法与C语言一致。 在计算机科学中，克努斯-莫里斯-普拉特字符串查找算法（，简称为KMP算法）可在一个字符串S内查找一个-{zh-hans:词; zh-hant:字;}-W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配對的字符。 这个算法由高德纳和沃恩·普…
字符串近似匹配
在计算机科学中， 字符串近似匹配（通常俗称为字符串模糊查询)，是一种字符串查找技术，用来近似匹配一个模式，而不是完全匹配。 概览 匹配的近似度用如下方法来度量：把字符串转换成完全匹配的字符串所需要的基本操作步数。这个数量被称为编辑距离。通常基本操作有： 插入: cot → coat 删除: coat → cot 替换: coat → cost 这三个操作可以泛化为使用NULL字符来替换原来的字符（这里使用来表示）： 插入: co****…
拉宾-卡普算法
在计算机科学中，拉宾-卡普算法（）或卡普-拉宾算法（），是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置，此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。 若要在一段文本中找出单个模式串的一个匹配，此算法具有线性时间的平均复杂度，其运行时间与待匹配…
Bitap算法
Bitap算法（或称为shift-or、shift-and、Baeza-Yates–Gonnet算法）是一种字符串近似匹配算法。该算法可判断给定的文本是否包含与定义模式“近似相等”的子字符串。其中，根据萊文斯坦距離如果子字符串和定义模式彼此在给定距离“K”之内，则该算法认为他们近似。该算法预先计算一组位掩码，其中每个位掩码的每一个元素都包含一个模式。然后，它可以通过按位操作以完成大部分工作。 可以将Bitap算法作为Unix软件开发工具…
博耶-穆尔字符串搜索算法
在计算机科学里，博耶-穆尔字符串搜索算法是一种非常高效的字符串搜索算法。它由和设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然博耶-穆尔算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽…
字串搜尋演算法
字串搜尋演算法（String searching algorithms）又稱字串比對演算法（string matching algorithms）是一种搜索算法，是字串演算法中的一類，用以試圖在一長字符串或文章中，找出其是否包含某一個或多個字符串，以及其位置。 最直觀的解法是比對，如下例中，在字符串haystack中找出字符串needle char haystack; char needle; int hlen, nlen, found…