strrep用法（stirred用法）

大家好，我是讯享网，很高兴认识大家。

所谓字符串匹配算法，简单地说就是在一个目标字符串中查找是否存在另一个模式字符串。如在字符串 “” 中查找是否存在 “” 字符串。

可以把字符串 “” 称为原始（目标）字符串，“” 称为子字符串或模式字符串。

本文通过如下种字符串匹配算法之间的差异性来探究算法的本质。

BF 算法是一种原始、低级的穷举算法。

如下使用长、短指针方案描述 BF 算法：

Tips： 辅助指针是长指针的替身，替长指针和短指针所在位置的字符比较。每次初始化长指针位置时，让辅助指针和长指针指向同一个位置。

查找成功： 短指针到达模式字符串尾部。

使用辅助指针替代长指针和短指针所在位置的字符进行比较。

测试：

输出结果：

以长指针为参照起点，需要比较时，以相对增量位置和短指针位置字符比较。

在原始字符串和模式字符串开始逐一比较时，最好不要修改长指针的位置，否则，在比较不成功的情况下，重修正长指针的逻辑有点繁琐。

算法直观，易于实现，但是缺少变通，是典型的穷举思想。

如果原始字符串的长度为，模式字符串的长度为。时间复杂度则是，时间复杂度较高。

算法 ( 指纹字符串查找) 在算法的基础上做了些改进，基本思路：

如下图示，和比较次后，才发现两者匹配不上，意味着前面的次比较，除了浪费时间，无其它意义。能不能通过一种算法，快速判断出本次比较是否有必要进行。

算法使用哈希函数算法杜绝了不必要的比较。

RK 的时间复杂度：

的代码逻辑和一样，但内置了哈希判断。如果原始子符串长度为，模式字符串的长度为。时间复杂度为，如果不考虑哈希冲突问题，理想状态下的时间复杂度可以为。

很显然算法比算法要快很多。

算法的本质是穷举，这是由计算机的思维方式决定的。

我们谈论“好”、“坏” 算法时，所谓的指能让穷举的次数少一些。比如前面的 RK 算法，通过一些特性提前判断是否值得比较，这样可以省掉很多不必要的内循环。

KMP 也是一样，也是尽可能减少比较的次数。

KMP 的基本思路和 BF 是一样的（字符串逐一比较）。但在算法做了性能上的优化。

让我们再次回到前面的比较流程中。如下图所示，在比较次后，辅助指针和短指针对应位置字符不相同，说明匹配失败。

的做法是，让长指针向右移一位，短指针恢复原始状态。再重新逐一比较。

但是，这里应该会有一个思考？难道前面的次成功的比较就没有一点可利用的价值吗？

讯享网

那就再回放，仔细观察一番。

会发现一个有趣的地方。部分匹配成功的字符串，在原始字符串中的后面的字符和模式字符串的前面的字符是相同的。如下填充灰**域。

直观告诉我们，长指针可以不用回到最初开始的位置，只需要让短指针稍微回一下。

如下图所示：

很明显示缩短了很多不必要的比较次数。

那么这个现象有没有通用性？

再分析如下个字符串的比较，即使前面有次比较成功，当匹配失败后，长指针确实可以不用移动，但是短指针必须回到最初位置，再重新开始。

那么在什么情况下可以让短指针只做稍微的移动？

说清楚这个问题之前，先理解几个概念：

一通前缀、后缀、交集概念说完后，但其结论很简单：仅当共同匹配成功的，其和有相同的部分时，方可以减少短指针的移动量。当相同部分越多，短指针移动的量就越小。

这里就有个问题又摆在面前。

如上的个问题，便是算法的核心。会把这些信息存储中 “”中，修改短指针的位置便是根据这个表中数据。

KMP 算法中的 “部分匹配表（PMT）” 是怎么计算出来的？

如前面图示，原始字符串和模式字符串逐一比较时，前位即是相同的，而存在最大长度的前缀和后缀 ‘’ 子串。意味着下一次比较时，可以直接让模式字符串的前缀和原始字符串中已经比较的字符串的后缀对齐。

这些信息都是从表中获取。所以，算法的核心是得到表。

现使用手工方式计算的值：

其实在算法中，没有直接使用表，而是引入了数组的概念，数组中的值是的值向右移动一位。

KMP算法实现： 先不考虑数组的算法，暂且用上面手工计算出来的值作为算法的已知数据。

上面的代码没有通用性的，现在实现求解数组的算法。

求也可以认为是一个字符串匹配过程，只是原始字符串和模式字符串都是同一个字符串。本质是在匹配成功的字符串中查找和相同子字符串的数量。

编码实现：

算法的时间复杂度可以达到。但是，如果模式字符串中不存在相同的前缀和后缀时，时间复杂度接近算法。

字符串匹配算法除了上述几种外，还有等算法。

从暴力算法开始，其它算法都是在尽可能减少计算次数，提高算法的运行速度。

strrep用法（stirred用法）

相关推荐