匹配算法有哪些，常用的字符串匹配算法最全详解
子字符串匹配
子字符串匹配算法的定义：
文本长度：N
模式字符串长度：M
有效位移：s
解决字符串的匹配算法有非常多，目前常用的有以下几种：
暴力查找
KMP 算法
Boyer-Moore算法
Rabin-Karp指纹字符串查找
字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。
常用算法
暴力查找
朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），它的主要特点是：
没有预处理阶段；
滑动窗口总是后移 1 位；
对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
需要 2n 次的字符比较；
KMP 算法
详细过程：
从左到右匹配，直到匹配到第一个字符相等，如下图所示，然后继续匹配后面的字符。
到了D，发现不对，这是如果暴力法，则直接将模式后移一位，重新匹配。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
在查找的一开始根据模式字符串，生成一张《部分匹配表》（Partial Match Table）
移动位数 = 已匹配的字符数 - 对应的部分匹配值
所以移动为数 = 6 - 2 =4
在这里插入图片描述
这个《部分匹配表》如何生成？
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
Boyer-Moore
几种常见的字符串匹配算法的性能比较：
KMP算法并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用Boyer-Moore算法。
详细过程：
首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。我们看到，"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。
依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。
"坏字符规则"：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置（如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1）
上图中，比较的是P和E，出现在第6位（0开始），然后P上一次位置是4，所以6-4=2
接着继续，一直比较到M：
本文地址：百科问答频道 https://www.neebe.cn/wenda/903057.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！
相关阅读
