嗨，这里是逻辑iOS技术号：一个让知识变得感性，让学习变得轻松！活跃的技术小站，希望给你的生活与技术带来意思不一样！关注公众号，回复“ 面试题 ”，即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且，还有我们向往的诗和大厂高薪工作~
方案一： BF算法
何为BF算法：
思路：
-
分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为1;
-
如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:
S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
-
如果j > T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0。
代码：
Status StrAssign(String T,char *chars){ int i; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1;i<=T[0];i++) T[i]=*(chars+i-1); return OK; }}int Index_BF(String S, String T,int pos){ int i = pos; int j = 1; while (i <= S[0] && j <= T[0]) { if (S[i] == T[j]) { i++; j++; }else { i = i-j+2; j = 1; } } if (j > T[0]) { return i - T[0]; }else{ return -1; }}方案二：RK算法
RK算法的求解过程：
哈希冲突：
-
如果不做哈希冲突二次核查 比较次数是n-m+1次; 那么时间复杂度为O(n);
-
但是要想解决冲突存在可能性.就需要添加二次核查! 那么 逻辑教育 就需要m次比对; 那么时间复杂度为O(n*m);
代码：
//d 表示进制#define d 26//4.为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.int isMatch(char *S, int i, char *P, int m){int is, ip;for(is=i, ip=0; is != m && ip != m; is++, ip++)if(S[is] != P[ip])return 0;return 1;}//3.算出最d进制下的最高位//d^(m-1)位的值;int getMaxValue(int m){int h = 1;for(int i = 0;i < m - 1;i++){h = (h*d);}return h;}/** 字符串匹配的RK算法* Author：Rabin & Karp* 若成功匹配返回主串中的偏移，否则返回-1*/int RK(char *S, char *P){//1. n:主串长度, m:子串长度int m = (int) strlen(P);int n = (int) strlen(S);printf("主串长度为:%d,子串长度为:%d\n",n,m);//A.模式串的哈希值; St.主串分解子串的哈希值;unsigned int A = 0;unsigned int St = 0;//2.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]//循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue//此时主串:"abcaadddabceeffccdd" 它的[0,2)是ab//此时模式串:"cc"//cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;//ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;for(int i = 0; i != m; i++){//第一次 A = 0*26+2;//第二次 A = 2*26+2;A = (d*A + (P[i] - 'a'));//第一次 st = 0*26+0//第二次 st = 0*26+1St = (d*St + (S[i] - 'a'));}//3. 获取d^m-1值(因为经常要用d^m-1进制值)int hValue = getMaxValue(m);//4.遍历[0,n-m], 判断模式串HashValue A是否和其他子串的HashValue 一致.//不一致则继续求得下一个HashValue//如果一致则进行二次确认判断,2个字符串是否真正相等.反正哈希值冲突导致错误//注意细节://① 在进入循环时,就已经得到子串的哈希值以及主串的[0,m)的哈希值,可以直接进行第一轮比较;//② 哈希值相等后,再次用字符串进行比较.防止哈希值冲突;//③ 如果不相等,利用在循环之前已经计算好的st[0] 来计算后面的st[1];//④ 在对比过程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]来求解s[i+1] . 简单说就是一边比较哈希值,一边计算哈希值;for(int i = 0; i <= n-m; i++){if(A == St)if(isMatch(S,i,P,m))//加1原因,从1开始数return i+1;St = ((St - hValue*(S[i]-'a'))*d + (S[i+m]-'a'));}return -1;}
（滑动显示更多 ）
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70005484/viewspace-2793488/ ，如需转载，请注明出处，否则将追究法律责任。
