单模式串匹配算法
BF算法
概念
- 在主串中，检查起始位置分别是0，1，2，...，n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。
- 时间复杂度是O(m*n)。
- 实现简单，对于处理小规模的字符串匹配很好用。
RK算法
概念
- 借助哈希算法对BF算法进行改造，是BF算法的升级版。
- 对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。
- 理想情况下，RK算法的时间复杂度是O(n)。
BM算法
概念
利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提供匹配效率。
实现
- 好后缀规则和坏字符规则
- 注意：好后缀规则可以独立于坏字符规则使用。
- 坏字符柜子的实现比较耗内存，为了节省内存，只能用好后缀规则来实现BM算法 //TODO
KMP算法
概念
- 根据规律遇到坏字符的时候，把模式串往后多滑动几位。
- 和BM算法本质非常类似。
多模式串匹配算法
Trie树
概念
- 即字典树，一个树形结构，专门处理字符串匹配的数据结构。
- 用来解决在一组字符串集合中快速查找某个字符串的问题。
- 利用字符串之间的公共前缀，将重复的前缀合并在一起。
实现
- 构造Trie树的每一步，都相当于往Trie树中插入一个字符串。
- 当所有字符串都插入完成之后，Trie树就构造好了。
应用
- 精确匹配查找这类问题更适用算列表或红黑树来解决。
- Trie树比较适合前缀匹配的字符串。
AC自动机
概念
在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上。
实现
- 将多个模式串构建成Trie树，在Trie树上构建失败指针。
- 在AC自动机中匹配主串。
哈希算法
概念
- 将任意长度的二进制值串映射为固定长度的二进制串，这个映射的规则就是哈希表。
- 通过原始数据映射之后得到的二进制值串就是哈希值
设计步骤
- 从哈希值不能反向推导出原始数据
- 对于输入的数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同。
- 散列冲突的概率非常小，对于不同的原始数据，哈希值相同的概率非常小。
- 哈希算法的执行效率要尽量高效，针对较长文本，也能快速地计算出哈希值。
应用
- 安全加密
- 唯一标识
- 数据校验
- 散列函数
- 负载均衡
- 数据分片
- 分布式存储。
