字符串的匹配在Java中都知道使用indexOf函数来实现，那么其匹配算法是怎么样的呢？
-
单模式串匹配算法
有BF算法、RK算法、BM算法、KMP算法；
-
多模式串匹配算法
Trie树；
单模式和多模式的区别就是一次遍历主串能否将多个模式的字符串都查找出来。
一、BF算法
英文全称为Brute Force，暴力匹配算法，匹配字符串的方法比较暴力，也比较简单易懂。其大概的思路就是：
- 假设待寻找的字符串为主串，长度为n；被寻找的字符串叫模式串，长度为m；其中n>=m；
- 在主串中，依次检查起始位置分别是0、1、2、...、(n-m)的且长度为m的总计(n-m+1)个子串，看看是否有和模式串匹配的。
BF算法过程示意
我们可以看到，在极端情况下，在主串aaaa...aab中寻找模式串aab，那么总共需要寻找(n-m+1)次，且每次都需要比对m次，那么时间复杂度将是(n-m+1)*m，即O(n*m)；但实际上并不会这么低效，因为我们的使用场景中主串和模式串都不会太长，而且在每个子串和模式串进行比对时，只要中途有一个不匹配，那么当前比对就会提前结束，因此大部分情况下，时间复杂度都会比O(n*m)要好。
二、RK算法
我们在BF算法的基础上引入哈希算法，我们不需要将每个子串与模式串逐个字符地进行比较，而是计算得出每个子串的hash值，然后和模式串的hash值进行比较，如果有相等的，那就说明有子串和模式串匹配上了。
RK算法对每个子串进行hash计算
虽然我们只需要比对模式串和子串的hash值就能得到匹配结果，次数为(n-m+1)，但是对每个子串进行hash计算的时候，是要遍历每个字符的，因此次数也是m，那么总的时间复杂度还是O(n*m)，并没有明显地提升。
那么我们该如何想出一个办法，使得每个子串hash值的计算时间得到提升呢？这就是RK算法的精髓，假设子串包含的字符集中元素个数为k，那么就用k进制数来代表这个子串，然后hash的过程就是将这个k进制的数转换为十进制的数，这个十进制的数就是该子串的hash值。
k进制数转换十进制数
相邻子串的hash值计算是有规律的，我们只需要遍历一次主串就能得到所有子串的hash值，算法复杂度为O(n)，而不是像原先一样，每个子串都需要O(m)的时间复杂度。
然后将模式串的hash值和所有子串的hash值进行比较，每次比较的时间复杂度是O(1)，总共比较(n-m+1)次，所以RK算法的总的时间开销为O(n)+O(1)*O(n-m+1)，即为O(n)，时间复杂度比BF算法更加高效。
当然，有hash的地方就有可能会存在hash冲突，有可能子串和hash值和模式串的hash值是一样的，但内容就是不一样，此时怎么办呢？其实很简单，对于hash值一样的子串，我们增加双保险，再比较一下这m个字符是否都一样即可，总的时间开销为O(n)+O(1)*O(n-m+1)+O(m)，即为O(n)。
如果极端情况下出现了很多hash冲突呢？我们对于每个和模式串相同hash值的子串都需要逐一再进行比较，那么总的时间开销就会为O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1)，即为O(n*m)，不过这种概率太小了，大部分情况下都不会这样。
三、BM算法
在真正的文本编辑器中查找和替换某个字符串时，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只适合不是很长的主串，RK算法则要设计一个冲突概率很低的hash算法，这个比较困难，所以实际使用的是BM算法，它是工程中非常常用的一种字符串匹配算法，效率也是最高的。
算法的思想和过程有些复杂，待以后整理。
四、KMP算法
KMP算法在本质上是和BM算法一样的。算法的思想和过程有些复杂，待以后整理。
五、Trie树
浏览器输入框中的智能输入匹配是怎么实现的，它是怎么做动态字符串匹配查找的呢？这就用到了Trie树。
又名字典树，是一种专门用来快速查找字符串前缀匹配结果的树形结构，其本质就是将所有字符串的重复的前缀合并在一起，构造一个多叉树。
Trie字典树的构造过程
其中，根节点不包含任何信息，每个节点表示一个字符，从根节点到红色节点的一条路径表示存储的一个字符串。当我们在如上Trie树中查找"he"时，发现"he"并非是一个字符串，而是"hello"和"her"的公共前缀，那么就会找到这两个字符串返回。
Trie树在内存中是如何存储的呢？因为每一个节点都可能是包含所有字符的，所以每一个节点都是一个数组（或者散列表），用来存储每个字符及其后缀节点的指针。
Trie树节点的散列表存储法
使用Trie树，最开始构建的时候，时间复杂度为O(n)，其中n为所有字符串长度之和，但是一旦构建完成，频繁地查询某个字符串是非常高效的，时间复杂度为O(k)，其中k为查找字符串的长度。
Trie树虽然查询效率很高，但是比较浪费内存，每一个节点都必须维护一个数组存放所有可能的字符数据及其指向下一个节点的指针，因此在所有字符串公共前缀并不多的时候，内存空间浪费地就更多了。这种问题其实也有对应的解决办法，我们可以不使用数组，而是使用有序数组、散列表、红黑树来存放，可以相应地降低性能来节省内存空间。
Trie树除了可以实现浏览器动态输入内容查找候选项的功能外，还可以实现多模式地敏感词匹配功能。假设我们需要对用户输入的内容进行敏感词检查，将所有的敏感内容用***代替，那么该如何实现呢？
首先我们可以维护一个敏感词字典，使用上述四种单模式匹配算法也可以实现，但是需要遍历N次用户输入的内容，其中N是所有敏感词的模式串，显得非常低效。但是我们如果将敏感词字典维护为一个Trie树，然后将用户输入的内容从位置0开始在Trie树中进行查询，如果匹配到红色节点，那么说明有敏感词；如果没有匹配到红色节点，就从用户输入内容的下一个位置开始继续在Trie树中查询，直至将用户输入内容遍历完，因此我们只是遍历了一遍主串。
然而更高效的多模式字符串匹配使用地更多的是如下的AC自动机。
六、AC自动机
如果把Trie树比作BF算法，KMP算法是BF算法的改进，那么AC自动机就是利用同样的思想改进了Trie树。
算法的思想和过程有些复杂，待以后整理。
网友评论