嗨，这里是逻辑iOS技术号：一个让知识变得感性，让学习变得轻松！活跃的技术小站，希望给你的生活与技术带来意思不一样！关注公众号，回复“ 面试题 ”，即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且，还有我们向往的诗和大厂高薪工作~

字符串匹配问题: 给你⼀个仅包含⼩写字⺟的字符串主串S = "abcacabdc",模式串T = "abd", 请查找出模式串在主串第⼀次出现的位置; 提示: 主串和模式串均为⼩写字⺟且都是合法输⼊。

方案一： BF算法

何为BF算法：

BF算法即暴风算法,是普通的模式匹配算法。BF算法的思想:将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。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算法的基本思想：

HASH！

如果两个字符串hash后的值不相同，则它们肯定不相同；如果它们hash后的值相同，它们不一定相同。

RK算法的基本思想就是：将模式串P的hash值跟主串S中的每一个长度为|P|的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，则再诸位比较之。

RK算法的求解过程：

将我们用来比较的字符串的全集设为∑={a,b,…,z}，设∑的长度为d=|∑|，则主串和模式串都可以看作是d进制数。例如只由数字组成的字符串，它的全集∑={0,1,2,3,4,5,6,7,8,9}，d=10。

设模式串为P，其长度为m，主串为S，其长度为n。则模式串P可以看作是一个m位的d进制数A，主串S可以看作是一个n位的d进制数。我们的模式匹配过程就是将A与主串中的每个长度为m的d进制数S[t…t+m-1] （t=0,1,2,…,n-m+1）的值做比较，所以整个模式匹配过程就变成了两个d进制数之间的比较过程。例如模式串为123，主串为65127451234，就是将十进制数123跟十进制数651, 512, 127, 274, 745, 451, 512, 123的逐个比较过程。

明确了匹配过程，下面就是求解A和求解S[t…t+m-1] （t=0,1,2,…,n-m+1）的过程：

（1）求解A。根据多项式计算方法，A = P[m-1] + d * (P[m-2] + d * (P[m-3] + …+ d * (P[1] + dP[0])…))

（2）求解S[t…t+m-1]。为了方便表示，我们设S[t…t+m-1] = St，则S[t+1…t+m] = St+1

假设已求得St，现在要求St+1，需要注意的是St+1是St去掉高位数据，其余的m-1位乘以d后再在最低位加一位得到。

于是St+1 = d * (St – dm-1S[t]) + S[t+m]

公式比较晦涩，举个例子看看吧。比如上面例子中主串是65127451234。S2=127，那么

S3=10×（127-102×1）+ 4 = 274

现在的问题是，如果A的值太大，比较的过程会比较耗时，这个时候我们可以将这个大数mod q(q是一个大素数)，同理，st也mod q,将两个取模之后的数相比较。

哈希冲突：

如果相等时,不要直接返回结果. 而是重新核实!

设计更复杂的哈希公式

如果不做哈希冲突二次核查比较次数是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+1

        St = (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;

}

（滑动显示更多）

iOS算法——字符串匹配

方案一： BF算法

方案二：RK算法