🌟前言
字符串匹配算法最经典的手段是BF算法，字符串匹配即给出一个主串S，根据模式串T中的字符串，找出在主串中第一次出现的位置，这个就是字符串匹配，简而言之即给一个规定的内容T，在大范围S中找到一个与之对应的，且第一次出现的位置。
BF算法
BF算法全称叫BruteForce，如本名一样，BF算法十分简单暴力，对主串和模式串进行逐个字符比较，中文名叫暴力匹配算法或者朴素匹配算法
而BF算法就是完成对模式串的移动，一位一位地往后移，然后从第一个字母开始比较，直到找到三个字母都相等的位置。
代码实现
首先我们先来写几个基本函数
/*生成一个其值等于chars的串T*/ Status StrAssign(String T,char *chars) { int i; if(strlen(chars)>MAXSIZE) return ERROR; else{ T[0]=strlen(chars); //T[0]存字符串的长度 for(i=1;i<=T[0];i++) T[i]=*(chars+i-1); return OK; } } /*清除字符串，直接令其长度为0*/ Status ClearString(String S) { S[0]=0; return OK; } /*打印字符串*/ void StrPrint(String T) { int i; for(i=1;i<T[0];i++) printf("%c",T[i]); printf("\n"); }
下面才是我们真正要开始写的BF算法的代码
先传进一个主串，模式串，然后再来一个pos(pos数值为多少，就代表从主串的第几个字母开始查找)
int Index_BF(String S,String T,int pos){ }
接着呢我们就写while循环，一步一步遍历我们的主串和模式串，分别用i,j变量。这里要注意的是，为了方便，我们默认把S[0]和T[0]存入他们各自的串长，也就是遍历从i=1和j=1开始，这样子也更方便我们书写代码，明确代码遍历到了哪一步
然后在while循环里添加if循环，判断S[i]和T[j]是否相等，相等就移到下一位，继续判断，移动就用i++和j++即可
如果不相等，证明遇到了不相同的字母，就让它俩回溯，让i回到初始位置，然后后移，而j回到1，又从模式串第一位开始判断，详细回溯解析看此代码后面的图解
int Index_BF(String S,String T,int pos){ //主串索引 int i = pos; //模式串索引 int j = 1; while (i<= S[0] && j<=T[0]){ //S[0]和T[0]的数值代表他们的长度 if(S[i] == T[j]){ i++; j++; }else{ //回溯，索引下标更改 i = i-j+2; j = 1; } } if(j>T[0]){ return i-T[0]; } return -1; }
if循环实现回溯图解
以此时i=3为例，正好判断到了第三位，S[i]和T[j]不相等，此时我们发现i = i -j +1是回到原位
那我们让其再+1，即i = i - j +2，就可以使其回到原位后再进一位，接着令j = 1，回到模式串第一位进行S[i-j+2]==T[j]的判断
此时i=i-j+2=2，S[2]不等于T[1]，又一次执行i = i - j +2，这时的i = 3，j = 1，通过这个循环，一步一步后移，实现了我们的BF算法，真的是简单粗暴，这个代码实现如果不能理解，就多看几遍图解，我相信你会有所收获
BF算法的时间复杂度很高，但有一个很好的优点就是：代码实现简单，在实际开发中，简单意味着，不容易出错，满足我们所说的KISS，咳咳，不是那个意思哈，是keep it simple and stupid（doge）
RK算法
RK算法是由两位发明者Rabin和Karp的名字来命名的，这个来历应该很容易理解吧（外国人都喜欢用自己名字命名一个新鲜事物哈哈）
相对于BF算法，RK算法比较的不是字母，而是数字，利用到哈希表这种算法，需要计算出哈希值
拿我们的例题来解释
模式串有三个字母，那我们就把主串分别以三个字母为一组子串，全部分隔出来，转化成我们的哈希值h1，h2，h3······，然后再和模式串比较，与哈希值相同的子串，就是我们要匹配到的，在主串中的位置
在这里边我们还可以稍作修改，例如我们没必要把所有子串都转化好，再进行与模式串的比较。为了去掉多余的步骤，我们可以边转化，边比较
假设我们的模式串为dda,此时转完第一个abd，不匹配；接着转第二个bdd，也不匹配；此时转到第三个，哎！是dda了，哈希值和模式串相同，这时我们就节省了后面dab,abc等子串的转化。
此时就有疑问了，我们该怎么把这模式串和拆出来的各个子串换算成哈希值呢？
首先我们先看一下十进制位的数字分解，以三位数为例
从上面的步骤看，abc的哈希值就是28，有了这套理论，我们就可以开始实践了
//RK算法 int getIndex_RK(String strOne, String strTwo){ //1、记录两个字符串的长度 int lengthOne = strOne[0]; int lengthTwo = strTwo[0]; //2、计算模式串的Hash值 long long twoHashValue = 1; for (int i = 1; i <= lengthTwo; i++) { int value = strTwo[i] - 'a' + 1; twoHashValue *= value; } //3、依次计算出主串每个子串的Hash值，边计算边比较 long long oneHashValue = 1; for (int i = 1; i <= lengthOne - lengthTwo + 1; i++) { if (i == 1) { for (int j = 1; j <= lengthTwo; j++) { int value = strOne[j] - 'a' + 1; oneHashValue *= value; } } else { //4、计算新子串的Hash值可以根据旧子串的Hash计算得出，减少重复计算 int valueOld = (strOne[i - 1] - 'a' + 1); int valueNew = (strOne[i + lengthTwo - 1] - 'a' + 1); oneHashValue = oneHashValue / valueOld * valueNew; } //5、Hash值相同需对比一下子串和模式串是否匹配（防止出现哈希冲突），匹配则返回index if (oneHashValue == twoHashValue) { int isOK = isMatch(strOne, i, strTwo); if (isOK == 1) { return I; } } } //6、如果没有找到匹配的子串，则返回-1 return -1; } //判断Hash值相等的字符串是否相等 int isMatch(String strOne, int index, String strTwo){ for (int i = 1; i <= strTwo[0]; i++) { if (strOne[index + i - 1] != strTwo[i]) { return 0; } } return 1; }
