数据结构与算法 - 字符串匹配

有主串 S = “abcacabdc”,模式串 T = “abd”,请查找出模式串在主串第一次出现的位置,注意:主串和模式串均为小写字母切都是合法输入。

BF算法

BF算法 Brute Force,其实就是暴力算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,弱相等,则继续比较S的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,一次比较下去,直到最后的的匹配结果。

// BF算法
int indexOf(char *S,char *T) {
    int i = 0,j = 0;
    int lenS = (int)strlen(S);
    int lenT = (int)strlen(T);
    while (i < lenS && j < lenT ) {
        // 比较两个字母若相同则继续比较
        if (S[i] == T[j]) {
            i++;
            j++;
        } else {
            // 找到上一次匹配的首位的下一位
            i = i-j+1;
            // j返回到子串T首位
            j = 0;
        }
    }

    if (j == lenT) {
        // 这里+1是为了将index转化为现实生活中的位置
        return i-lenT+1;
    } else {
        return -1;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    int index = indexOf("abcdex""ex");
    printf("第一个匹配的位置是 %d \n",index);
    return 0;
}
-----
Hello, World!
第一个匹配的位置是 5 
1
2
3
4
上面BF算法我们可以发现我们需要去遍历每一个字符,有那么一种情况是:
S = "aaaaaaaaaaaaaaaabdhsdf"
T = "aaaaaaaab"
这个时候我们会发现每次都是在最后一位发现不同,这样我们其实浪费了很多次循环,这样就出现了另外一中算法:RK算法

RK算法

RK算法 是由 Rabin 和 Karp 共同提出的一个算法,RK算法是对BF算法的一个改进,只进行一次比较就判定两者是否相等。RK的大体思想跟BF一样,把主串拆分成若干个子串,循环遍历每一个子串和目标串T进行比对,但是其利用了Hash算法的设计思想,每个子串都对应唯一一个哈希值,我们设计一个尽量不冲突的哈希算法来求每个子串的哈希值,一一匹配直到相等即可。

哈希函数设计

那么哈希算法如何设计呢?我们知道字符串的一一比较显然不如数字比较来的快

1
2
例如:
主串 S = 6541451234 T = 123 就是将123跟十进制651,541,414,145,451,512,123,234进行一一比较大小。

而对于十进制数来说

1
123 = 1*10*10 + 2*10 + 3

所以我们也设计类似的进制数,那么针对26位字母,当然26进制是最好的,这样会尽可能的避免冲突发生的可能性。

RK 算法中还用到一个技巧就是,只要算出第一个数字,后面的数字就可以根据第一个数字一一计算出,具体我们以十进制为例

1
2
3
4
5
6
例如:
主串 S = 6541451234 T = 123
首先我们得出 654 = 6*100 + 5*10 + 4
那么第二个数字 541 = (654-6*100)*10 + 1
第三个数字就是 414 = (541-5*100)*10 + 4
也就是 (前一个数 - 最高位 * (位数-1)*进制数)*进制数 + 下一个个位数

具体算法如下:

#define d  26 // 进制数

// 即使我们求出了结果,但是为了验证是否冲突加一个验证
int isMatch(char *S, int i, char *P, int m)
{
    int is, ip;
    for(is=i, ip=0is != m && ip != m; is++, ip++)
        if(S[is] != P[ip])
            return 0;
    return 1;
}

// 计算最高位的幂次方 比如三位子串就是26的平方
int getMaxValue(int Tlength{
    int value = 1;
    for (int i = 0; i < Tlength-1; i ++) {
        value *= d;
    }
    return value;
}

// RK算法
int RK(char *S, char *T{
    int slen = (int)strlen(S);
    int tlen = (int)strlen(T);

    int hashS = 0;
    int hashT = 0;
    // 分别保存两个字符串的首个哈希值
    for (int i = 0; i < tlen; i++) {
        hashS = hashS*d +(S[i]-'a');
        hashT = hashT*d +(T[i]-'a');
    }

    int hValue = getMaxValue(tlen);

    for (int i = 0; i <= slen-tlen; i++) {
        // 如果哈希值相等就是找到了
        if (hashS == hashT) {
            // 验证是否真的相同
            if (isMatch(S, i, T, tlen)) {
                return i+1;
            }
        }
        // 更新hashS
        hashS = (hashS- (S[i]-'a')*hValue)*d + (S[i+tlen]-'a');
    }
    return -1;
}

int main(int argc, const char * argv[]{
    // insert code here...
    printf("Hello, World!\n");
    int index = RK("abcdex""ex");
    printf("第一个匹配的位置是 %d \n",index);
    return 0;
}
-----
Hello, World!
第一个匹配的位置是 5 

KMP 算法

D.E.KnuthJ.H.MorrisV.R.Pratt 共同发表模式匹配算法,称之为 克鲁特-莫里斯-普拉特算法

上面我们讲述了 BF算法,题目如下:

我们有主串 S = “abcabdcdabcf”,

匹配串 T = “abcf”

我们依次遍历主串和匹配串每个位置的字符,这里我们默认字符串的第0个位置保存的是字符串的长度,也就是说我们的串起始位置都是从1开始。

第一步

依次比较 s[i]T[j],如果他们的值相同, i++ ,j++ 直到 i=4,j=4 的时候发现它们俩对应的字符不同,那么来到第二步:

第二步

i=2,j=1 发现他们的值不同,来到第三步:

第三步:

i=3,j=1 发现他们的值不同,来到第四步:

第四步

从第一步到第四步我们都是依次进行遍历比较,里边有我们能优化的地方吗:

根据上图我们知道第一步我们已经比较到 i=4 的时候不同,那么我们的第二步第三步 明显是可以省略的,所以为了优化,我们应该直接跳到第四步。

那么这个很容易理解,因为我们的子串T 内部的字符都不相同,那么我们看一个复杂一点的例子:

这个时候问题来了,下一步我们该从哪开始呢:

如上图,很显然子串的首两位 ab 是不需要再进行比较的,因为我们在上面进行比较的时候已经比较过了,这个最主要的原因就是:

我们当前匹配成功的那一部分字符串有相同的前缀和后缀

这样理解起来就会简单的多,前缀和后缀相同那么如果匹配到后缀的位置,前缀就不用再比较了,所以问题的核心就是找到子串的每一部分对应的跳转,也就是子串任意位置匹配失败而导致重新配的位置,这里业界统一用一个 next[…] 数组来保存字符串 T 的每个字符匹配失败对应的下次 j 跳转的位置,那么只要匹配失败,我们就将下一次比较的j = next[j] 即可。

next数组

为了方便我们默认 next[1] = 0

1
T = "abcdex"
  • 当 比较到a不相等的时候,next[1] = 0
  • 当比较到b不想等的时候,它前面的范围内只有一个字符 a 那么下次比较还是要跳到j=1 所以next[2] = 1
  • 以此类推,因为T串中没有相同的字符所以其每个位置只要发现不同,都要跳转到j= 1 的位置执行,所以针对 此T 串的 next = [0,1,1,1,1,1]

我们再来对比一个复杂一点的:

1
T = "abcab"
  • 当 比较到a不相等的时候,next[1] = 0

  • 当比较到b不相等的时候,它前面的范围内只有一个字符 a 那么下次比较还是要跳到j=1 所以next[2] = 1

  • 当比较到c不相等的时候,它前面的范围内的字符是 ab 那么下次比较还是要跳到j=1 所以next[3] = 1

  • 当比较到第二个a不相等的时候,它前面的范围内的字符是 abc 那么下次比较还是要跳到j=1 所以next[4] = 1

  • 当比较到第二个b不相等的时候,它前面的范围内的字符是 abca,这里就要注意了,该串有相同的前缀和相同的后缀a 那么当我么再跳转的时候,应该是直接比较 b 这个位置才对,我们相同的前缀和后缀字符串长度是1,那么我们下一次比较的位置应该在相同前缀或后缀长度的下一个字符处,所以next[5] = 2

    所以针对此种情况 next = [0,1,1,1,2]

结合上述对next 数组的理解,我们用代码来实现:

//----KMP 模式匹配算法---
//1.通过计算返回子串Tnext数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
    int i,j;
    j = 1;
    i = 0;
    next[1] = 0;
    //abcdex
    //遍历T模式串, 此时T[0]为模式串T的长度;
    //printf("length = %d\n",T[0]);
    while (j < T[0]) {
        //printf("i = %d j = %d\n",i,j);
        if(i ==0 || T[i] == T[j]){
            //T[i] 表示后缀的单个字符;
            //T[j] 表示前缀的单个字符;
            ++i;
            ++j;
            next[j] = i;
            //printf("next[%d]=%d\n",j,next[j]);
        }else
        {
            //如果字符不相同,则i值回溯;
            i = next[i];
        }
    }
}

next 数组已经求解出来了,接下来我们就具体实现 KMP算法

//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){

    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;

    //定义一个空的next数组;
    int next[MAXSIZE];

    //对T串进行分析,得到next数组;
    get_next(Tnext);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {

        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }

    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }

}

KMP的优化

我们来看另外一个特殊的例子:

当我们比较到j=6 的时候发现不一样,这个时候我们就应该跳转 j=next[5]=5

当我们比较到j=6 的时候发现不一样,这个时候我们就应该跳转 j=next[4]=4

然后依次类推,直到循环到 j=1 ,那么这种特殊情况就挺恶心的,因为我们已经比较了a,但是依赖于上述程序的话只能这么走,但是确实有很多不必要的比较,其实我们是想直接这样:

基于此,我们针对这种特殊情况对 KMP 算法进行优化,首先就是要对 next数组进行优化:

//求模式串Tnext函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
    int i,j;
    j = 1;
    i = 0;
    nextVal[1] = 0;
    while (j < T[0]) {
        if (i == 0 || T[i] == T[j]) {
            ++j;
            ++i;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i] != T[j])
                nextVal[j] = i;
            else
            //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[j] = nextVal[i];
        }else{
            i = nextVal[i];
        }
    }
}

这样的话我们求出来的next = [0,1,1,1,1,1]

//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP2(String S,String T,int pos){

    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;

    //定义一个空的next数组;
    int next[MAXSIZE];

    //对T串进行分析,得到next数组;
    get_nextVal(Tnext);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {

        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }

    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }

}

这种特殊情况,用这种优化的方法处理起来会更加的快捷,但是普通情况下还是第一种最好,所以算法的优劣还是要依据具体的应用场景和实际的情况,不能一概而论

总结

这篇文章主要讲述了字符串匹配的三种方法,各有优劣,其中KMP 算法的理解上可能会有些难度,但是仔细去琢磨就会慢慢弄懂其中究竟,希望这篇文章能给大家讲清楚。