题目: 有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模式串在主串中第一次出现的位置
提示: 不需要考虑字符串大小写问题, 字符均为小写字母
使用算法：BF算法、RK算法

BF算法

是什么

一般叫做暴力算法，也叫做朴素算法。主要思想就是把目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

BF算法示意图

思路

时间复杂度：O(n*m)

分别初始化i,j。i和j分别从主串S 和模式串 T 第一个字母开始
如果相等，则继续下一个字符
如果不想等，主串回退到匹配j的下一个位置
遍历结束查看是否匹配的到

代码

#define MAXSIZE 40    /* 存储空间初始分配量 */
typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */

int findIndexBF(String target,String content,int startPosition) {
    int i = startPosition; // 从指定位置开始
    int j = 1;
    
    // 如果i 小于target长度，且j 小于content长度，循环继续
    while (i < target[0] && j < content[0]) {
        if (target[i] == content[j]) {
            // 内容相同，继续
            i ++;
            j ++;
        } else {
            // 没有匹配到，那么主串索引回退到已经匹配过的首位
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > content[0]) {
        return i - content[0];
    }
    return -1;
}

int main(int argc, const char *argv[]) {
    printf("Hello, World!");
    return 0;
}

RK算法

是什么

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。
如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。
因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
示意图如下：

RK算法示意图

对比BF算法

RK算法的全称叫Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。其实是BF算法的升级版本，在BF算法中，需要每次都进行字符串的匹配，每次需要检查模式传是否与主串相等，所以时间复杂度是O(n*m)。
而RK算法是通过对比字符串的哈希值（散列），哈希是数字，对比哈希的效率相对于比较字符串来说，肯定是高了不少的，但是从时间效率上来说，到这一步并没有比BF少了多少。

而哈希算法的巧妙之处就在于此了，在计算字符串的哈希值时，由于a-z是26个字母，因此可以类比于十进制，用作26进制来计算，下面来举个🌰

进制

在对比模式串的时候可以发现相邻子串的一些规律，相邻的2个子串 s[i] 与 s[i+1] (i表示子串从主串中的起始位置,子串的长度都为m)，对应的哈希值计算公式有交集，也就说我们可以使用 s[i-1] 计算出 s[i] 的哈希值。
s[i+1] 实现上是上一个s[i]去掉最高位数据,其余的m-1为字符乘以 d进制. 再加上最后一个为字符得到,推导如下

相邻子串数值比较

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。

思路

求出对应模式串的哈希值，主串分解子串哈希值
求得子串与主串中0~m字符串的哈希值(计算子串与主串0-m的哈希值)
获取d^{m-1值(因为经常要用d}m-1进制值)
遍历[0,n-m], 判断模式串HashValue A是否和其他子串的HashValue 一致.
不一致则继续求得下一个HashValue
如果一致则进行二次确认判断,2个字符串是否真正相等,防止哈希值冲突导致错误

注意细节:

在进入循环时,就已经得到子串的哈希值以及主串的[0,m)的哈希>值,可以直接进行第一轮比较

哈希值相等后,再次用字符串进行比较.防止哈希值冲突

如果不相等,利用在循环之前已经计算好的st[0] 来计算后面的st[1]

在对比过程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]来求解s[i+1] . 简单说就是一边比较哈希值,一边计算哈希值

代码

// 防止hash值相等，字符串不相等的情况
bool isMatch(char *mainString, int index, char *matchString, int matchLength) {
    for (int i = 0; i < matchLength; i ++) {
        if (mainString[index + i] != matchString[i]) {
            return false;
        }
    }
    return true;
}

int RK(char *mainString,char *matchString) {
    int d = 26;
    int m  = (int)strlen(mainString); // 主串长度
    int n  = (int)strlen(matchString); // 模式串长度
    
    unsigned int mainHash  = 0; // 子串hash
    unsigned int matchHash   = 0; // 模式串hash
    
    //d^m-1值(因为经常要用d^n-1进制值)
    int hValue = 1;
    
    //求得子串与主串中0~n字符串的哈希值[计算子串与主串0-n的哈希值]
    //循环[0,n)获取模式串A的HashValue以及主串第一个[0,n)的HashValue
    for(int i = 0; i < n; i++){
        matchHash = (d * matchHash + (matchString[i] - 'a'));
        mainHash = (d * mainHash + (mainString[i] - 'a'));
        hValue = i > 0 ? hValue * d : hValue; // 计算d^n-1进制值
    }
    
    for (int i = 0; i <= m - n; i++) {
        if (matchHash == mainHash && isMatch(mainString, i, matchString, n)) {
            return i;
        }
        mainHash = (mainHash - hValue * (mainString[i] - 'a')) * d + (mainString[i+n] - 'a');
    }
    return -1;
}

BF、RK算法

BF、RK算法

BF算法

是什么

思路

代码

RK算法

是什么

对比BF算法

思路

代码