字符串匹配算法
字符串匹配算法
BF 算法
bf算法又叫做暴力匹配算法，核心思想为：主串中，检查起始位置分别为0,1，2,3，…n-m 且长度为m的n-m+1个子串，看有没有跟模式串匹配的，（比如 在字符串A中查找字符串B，那么A为主串，B为模式串）
- 匹配规则
- 时间复杂度：比如模式串长度为m，主串长度为n，每次都要比对m个字符，要比对n-m+1次，所以最坏情况下时间复杂度为o(n*m)
RK 算法
RK算法叫Rabin-Karp算法，核心思想为：在对BF算法中，每次需要比较主串的子串与模式串挨个对比每个字符，所以时间复杂度比较高，所以RK算法改进了BF算法，引入了哈希算法，通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后与模式串的哈希值比较，如果相等，就认为相等，（暂时没考虑哈希冲突）
- 匹配规则
- 时间复杂度：模式串与主串的子串之间比较时间为o(1),总共需要比较n-m+1个子串，所以时间复杂度为o(n)
BM算法
BM算法是非常高效的字符串匹配算法，核心思想为：在BF算法中，模式串与主串匹配，遇到不匹配的，向后移动一位，在从头开始匹配，在BM算法中本质其实即使在匹配中，若子串中的一位未出现在模式串中，就移动模式串，移动到未匹配的字符后面，这样效率就比BF效率高出很多。具体来说，BM算法包含两部分，分别为坏字符串规则，和好后缀规则，来决定向后移动的位置
- 坏字符规则：
从模式串的末尾往前倒着匹配，当某个字符串没法匹配时，把这个字符串叫做坏字符
拿坏字符d在模式串中查找，发现模式串中不存在d这字符，直接将模式串滑动到d的后面，直接从后一位开始比较
发现坏字符a在模式串中是存在的，将模式串的a与主串的a上下对齐，再重新开始匹配
向后移动的位置规律：
将i设置成 坏字符对应的模式串的下标“2” 既i=2，将j设置成模式串的坏字符下标 “0” 既 j=0；如果模式串中不存在坏字符，则j=-1 ，所以移动的位数为d=i-j，但是对于字符串这种情况下
i-j 就小于0了，这就会导致匹配规则往后移动了，所以需要好后缀规则来决定移动的位数 - 好后缀规则：
当模式串与主串匹配时，最后连个字符匹配，倒数第三个为坏字符，我们称f，a 为好后缀，滑动规则为，我们称主串好后缀为{s-a}，我们在模式串中寻找与{s-a}相同的字符串，称为{s-b}
如果模式串中有匹配到好后缀，那么就将{s-b}与{s-a}对齐,如果没有匹配到，那么就直接滑动到主串{s-a}的后面 - 异常状况：
像图中这样，好后缀{s-a}在模式串中找不到，所以直接滑动到{s-a}后面，直接导致本来能够匹配的字符串，因为滑动过多匹配不上，所以还需要另外处理一下，当好后缀{s-a} 在模式串中，无法匹配到字符串时，为了避免以上情况的产生，我们需要获取好前缀{s-a}的后缀子串 ：a （后缀子串：abc的字串 bc，c），获取模式串的前缀(af)子串(a (abc前缀子串 a,ab ))，将模式串滑动到图示位置 - 如何选择：我们分别计算好坏字符滑动的位数和好后缀滑动的位数，比较两个位数大小，选取最大的作为滑动的位数