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

字符串匹配算法是面试中的重点考察面试者基本功的一种算法类型。所谓字符串匹配，就是查找子串在主串中的位置，关于字符串匹配问题，常见的算法有 BF，RK和KMP。今天我们一起来探索 BF 和 RK 算法。

BF 算法

BF 算法全程是 Brutal-Force 算法，也称暴力匹配算法。

首先，先理清楚了暴力匹配算法的流程及内在的逻辑： 如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

1. 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
2. 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

这种方法看起来比较笨，就是每次匹配失败后，都需要回到主串上一次起始位置的下一个字符进行比较，而最终的时间复杂度取决于主串的长度和子串的长度，也就是 O(MN) (M为主串的长度，N为子串的长度)。

下面我们给出具体的思路:

BF算法
思路:
1. 分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前正待比较的字符位置, i 初值为 pos , j 的初值为 1;
2. 如果 2 个串均为比较到串尾,即 i 和 j 均小于等于 S 和 T 的长度时, 则循环执行以下的操作:

• S[i] 和 T[j] 比较,若相等,则 i 和 j 分别指示串中下一个位置,继续比较后续的字符;
• 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较; 这里本身的 i = i - (j - 1)，然后因为这里我们设计的数据结构是字符数组第 0 位存储的是整个字符的长度，所以需要再加上一个 1，也就得到了 i = i - (j -1) + 1 = i - j + 2;

1. 如果 j > T.length, 说明模式 T 中的每个字符串依次和主串 S 中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号 (i-T.length) ;否则匹配失败,返回0;

#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 40    /* 存储空间初始分配量 */
typedef int Status;   /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */

/* 
   生成一个其值等于chars的串T 
   字符串转字符数组    
*/ 
Status StrAssign(String T,char *chars)
{
    int i;
    // 如果字符串长度大于最大值，返回 ERROR
    if(strlen(chars) > MAXSIZE)
        return ERROR;
    else
    {
        // 将字符串长度存储在字符数组的第0个位置
        T[0]=strlen(chars);
        // 从第一个位置开始往字符数组里面填充字符
        // 因为参数 chars 是字符串指针，其实是指向的字符串的起始位置的内存地址
        // 这里通过 * 间接访问操作符作为右值相当于取值操作，同时 chars + i - 1 相当于
        // 从第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;
}

/*  输出字符串T。 */
void StrPrint(String T)
{
    int i;
    for(i = 1;i <= T[0];i++)
        printf("%c",T[i]);
    printf("\n");
}

/*  输出Next数组值。 */
void NextPrint(int next[],int length)
{
    int i;
    for(i = 1;i <= length;i++)
        printf("%d",next[i]);
    printf("\n");
}

/* 返回串的元素个数 */
int StrLength(String S)
{
    return S[0];
}

// 核心算法
// 参数: 
// 主串 S
// 子串 T
// 在主串中进行搜索的位置 pos
int Index_BF(String S, String T,int pos){

    //i 表示主串 S 中当前位置下标值，若 pos 不为1，则从 pos 位置开始匹配
    int i = pos;
    //j 用于子串 T 中当前位置下标值
    int j = 1;

    //若 i 小于 S 的长度并且 j 小于 T 的长度时，循环继续
    while (i <= S[0] && j <= T[0]) {

        // 比较的 2 个字母相等, i 和 j 同时移动到下一个位置,则继续比较
        if (S[i] == T[j]) {
            i++;
            j++;
        }
        else
        {
            // 不相等,则指针后退重新匹配
            // 本身 i 是需要回退到当前遍历主串起始位置的下一个位置，所以是
            // i - (j - 1)，而由于第 0 个位置是存储的长度，所以需要再加一个 1
            i = i - (j - 1) + 1;

            // j 退回到子串T的首位
            j = 1;
        }
    }

    //如果 j > T[0] , 则说明匹配成功
    if (j > T[0]) {
        //i 主串遍历的位置 - 模式字符串长度 = index 位置
        return  i - T[0];
    } else{
        return -1;
    }

}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("字符串模式匹配!\n");

    int i, *p;
    String s1,s2;

    StrAssign(s1, "abcdex");
    printf("s1子串为");
    StrPrint(s1);


    StrAssign(s2, "xe");
    printf("s2子串为");
    StrPrint(s2);

    i = Index_BF(s1, s2, 1);
    printf("i = %d\n",i);

    return 0;
}

RK 算法

RK 算法的全称是 Rabin-Karp 指纹字符串查找算法 ，从名称上我们可以看出，RK 算法是由两位科学家共同提出的。

在计算机科学中，Rabin–Karp算法或Karp–Rabin算法（英文：Rabin–Karp algorithm或Karp–Rabin algorithm），是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转散列以快速筛出无法与给定串匹配的文本位置，此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。

若要在一段文本中找出单个模式串的一个匹配，此算法具有线性时间的平均复杂度，其运行时间与待匹配文本和模式串的长度成线性关系。虽然平均情况下，此算法表现优异，但最坏情况下，其复杂度为文本长与模式串长的乘积。当在文本中搜寻多个匹配时，其具有线性时间的平均复杂度（与文本串长、模式串长、模式串所有匹配总长三者的和成线性关系）。相对地，另一种用于找出模式串所有匹配的AC自动机算法的最坏情况复杂度与文本串长、模式串长、模式串所有匹配总数（而非总长）成正比。

此算法的一个实际应用为内容相似度检验（如论文查重）。在给定原材料与待查重论文的情况下，此算法可以迅速在论文中搜寻原材料中的句子，同时忽略诸如大小写与标点等细节。由于原材料中的字符串过多，故单字符串搜索算法在此处不适用。

Rabin-Karp 算法《维基百科》

关于 RK 算法，我们要先搞清楚什么是散列函数。

散列函数

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

由上面的定义我们可以得出简单的结论，两个元素相同，那么散列值必然相同，而散列值相同并不能说明两个元素相同，这是因为不存在所有元素都有自己哈希值的情况，也就是说，两个不同的元素有一定可能性会有相同的哈希值。这种情况被称为哈希碰撞，在 iOS 底层原理探索的时候，我们已经了解到在 iOS 底层方法缓存设计中，当哈希表的装载因子超过 0.75 的时候，就需要解决哈希冲突，iOS 采用的是对哈希表进行扩容，这种处理方式可以归为 开放寻址法 。

要解决字符串匹配问题，RK 算法的核心思想就是通过散列函数计算出子串的散列值，然后再去主串中求解对应长度的串的散列值。但是这里有一个注意点，RK 算法并不是一次性计算完所有等于子串长度的串的散列值，因为这种方式效率很低下，RK 算法采用的是边计算边比较的思想。什么意思呢？也就是说从主串的第一个位置开始计算，每次计算对应子串长度的串的散列值，然后再与子串的散列值进行比较。如果不匹配，那么就从第二个位置开始计算对应子串长度的串的散列值，然后，然后再与子串的散列值进行比较，以此类推直到找到匹配为止。

那么根据上面的分析，RK 算法必然会设计一个非常好的散列函数，来减少散列碰撞的可能性。话不多说，我们直接上代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//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;
}

int main()
{
    char *buf="abcababcabx";
    char *ptrn="abcabx";
    printf("主串为%s\n",buf);
    printf("子串为%s\n",ptrn);

    int index = RK(buf, ptrn);
    printf("find index : %d\n",index);

    return 1;
}