字符串匹配算法
单模匹配
BruteForce
暴力匹配算法
Rabin-Karp
P进制Hash算法 O(N)时间复杂度
Boyer-Moore
BM算法核心思想是,利用模式串本身的特点,在模式串中某个字符与主串不能匹配的时候,将模式串往后多滑动几位,
以此来减少不必要的字符比较,提高匹配的效率。BM算法构建的规则有两类,坏字符规则和好后缀规则。
好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存,为了节省内存,我们可以只用好后缀规则来实现BM算法
KMP
KMP算法借鉴BM算法的思想,可以总结成好前缀规则
多模匹配
Trie
可以对Trie进行内存优化,有序数组、平衡数、跳表等