【串】串的模式匹配算法(BF+KMP)(C语言)

串的模式匹配算法(C语言)

1.字符串的初始化函数

定义一个字符数组S,我们用第0位来存储该字符串的长度,其余位置顺序存储该字符串。(字符串的首位从1开始)

代码实例:

#include <stdio.h>
#include <string.h>

#define N 100   /*静态定义数组的长度*/

typedef char String[N];          // String s1  等价于   char s1[N]

int StrAssign(String T, char *chars)   // 初始化字符串
{
    T[0] = strlen(chars);
    for (int i = 1; i <= strlen(chars); i ++ ) {
        T[i] = *(chars + i - 1);
    }
    return 1;
}

int main()
{
    String s1;
    StrAssign(s1, "hello world!");
    printf("%s", s1);    // 输出该字符串
    printf("\n%d", s1[0]);   // 输出字符串的长度
    return 0;
}

2.朴素模式匹配算法

思想:
从主串S的第pos位开始逐位与模式串T比较,若对应位置的字符均相等,则匹配成功,返回模式串T在主串S中的位置,否则模式串T整体向后移动一位重新从头开始比较(例如,当前是从主串S的第pos位与模式串T的第1位开始比较,则下一次就是主串S的第pos+1位与模式串T的第1位开始比较),直到匹配成功或无法再继续匹配(主串S剩余未被匹配的长度小于模式串T的长度)。
若匹配成功,返回模式串T在主串中的位置;否则返回0

代码实例:

#include <stdio.h>
#include <string.h>

#define N 100

typedef char String[N + 1];

int StrAssign(String T, char *chars)   /*初始化字符串*/
{
    T[0] = strlen(chars);
    for (int i = 1; i <= strlen(chars); i ++ ) {
        T[i] = *(chars + i - 1);
    }
    return 1;
}

/*返回子串T在主串S中第pos个字符之后的位置,若不存在,则返回0*/
int Index(char S[], char T[], int pos)
{
    int i = pos;   // i用于主串中当前位置下标
    int j = 1;     // j用于字串T中当前位置下彪
    while (i <= S[0] && j <= T[0]) {   // 若i小于S 且 j小于T的长度时循环
        if (S[i] == T[j]) {  // 两字符相等这则继续
            i++;
            j++;
        }
        else {
            i = i - j + 2; // 回到上一次匹配位置的下一位
            j = 1;
        }
    }
    if (j > T[0])  return i - T[0];   // j>T[0]说明匹配成功
    else  return 0;
}


int main()
{
    String s1, s2;
    StrAssign(s1, "abcccdef");
    StrAssign(s2, "cd");
    printf("%d", Index(s1, s2, 1));
    return 0;
}

3.KMP模式匹配算法

朴素模式匹配算法的低效性:
通过朴素模式匹配算法我们可以知道,当主串S为:abcdefghijk… ,模式串T为:abcdek 时,假设我们从S的第一位开始比较,则前5位字符均相等,第6位字符不等,按照朴素模式匹配的思路,我们此时应该从S的第2位字符’b’(S[2])开始重新与T的第一位’a’(T[1])比较,不等,然后让S[1]与T[1]比较,还是不等… 对于T来说,T[1]与后面的’bcdek’均不等,那么如果T的前五位都与S的前五位相等,而T[1]与T[2]、T[3]、T[4]都不相等,则T[1]与S[2]、S[3]、S[4]也不等,这些比较都是无效的比较,是算法可以优化的地方。

下面看T[1]与T后面的字符相等的情况,假设主串S为:abcababca ,模式串T为:abcabx ,我们可以看到,S与T的前5位都相同,第6位不同,且T[1]与T[2]、T[3]不相同,那么T[1]与S[2]、S[3]也不相同,可以直接跳过这些步骤,从S[4]与T[1]开始比较。 又因为T[1](a)与T[4](a)相等,T[2](b)与T[5](b)相等,且而 T的前五位与S的前五位相等(自然T[4]T[5](ab)与S[4]S[5]相等)。 那么可以推出:T[1]T[2]与S[4]S[5]也是相同的,我们可以直接从T[3]与S[6]开始比较。 我们可以发现在上述的比较过程中,主串S的比较位置并没有回溯,我们先从S[1]–S[5]与T[1]–T[5]进行比较,然后直接从T[6]与T[3]进行比较。这种方法就是KMP模式匹配算法。

从上面的例子我们知道,在KMP算法中,主串S的比较位置是不进行回溯的,相当于我们在比较的过程中主串不动,不断移动模式串T,例如在刚才的例子中,当S[6]与T[6]不相等时,我们通过推算,将模式串T向后移动了3个单位,让T[3]来与S[6]比较,在KMP算法中,存在一个next数组用来记录在模式串T中每个字符的回溯位置,next数组中的值与主串S无关, 经过计算,next[6] = 3,所以当第6个位置不匹配时,我们直接将模式串T回溯到第三位继续匹配。那如何计算next数组的值呢?

3-1.手推next数组

以模式串T=ababaaaba 为例,j表示字符串T中字符的位置,下方红色部分为next数组计算的方法。

【串】串的模式匹配算法(BF+KMP)(C语言)

3-2.next数组代码实例

我们仍求ababaaaba的next数组,程序的结构为:0 1 1 2 3 4 2 2 3,与我们在上面手推的结果是一致的。

#include <stdio.h>
#include <string.h>

#define N 100

typedef char String[N];          // String s1  等价于   char s1[N]

int StrAssign(String T, char *chars)   // 初始化字符串
{
    T[0] = strlen(chars);
    for (int i = 1; i <= strlen(chars); i ++ ) {
        T[i] = *(chars + i - 1);
    }
    return 1;
}

// 返回字串T的next数组
void get_next(String T, int *next)   
{
    int i, j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i < T[0]) {   // T[0]为串T的长度
        if (j == 0 || T[i] == T[j])  { // T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];  // 若字符不相等,则j值回溯
    }
}

int main()
{
    String T;
    int next[N] = {0};
    StrAssign(T, "ababaaaba");
    get_next(T, next);
    for (int i = 1; i <= T[0]; i ++ ) {
        printf("%d ", next[i]);
    }
    return 0;
}

3-3.KMP算法实例

求字串 aba 在 主串 ababaaaba4个位置后 首次出现的位置,程序输出结果为7

#include <stdio.h>
#include <string.h>

#define N 100

typedef char String[N];          // String s1  等价于   char s1[N]

int StrAssign(String T, char *chars)   // 初始化字符串
{
    T[0] = strlen(chars);
    for (int i = 1; i <= strlen(chars); i ++ ) {
        T[i] = *(chars + i - 1);
    }
    return 1;
}

// 返回字串T的next数组
void get_next(String T, int *next)   
{
    int i, j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i < T[0]) {   // T[0]为串T的长度
        if (j == 0 || T[i] == T[j])  { // T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];  // 若字符不相等,则j值回溯
    }
}

// 返回字串T在主串S中的第pos个字符之后的位置,若不存在则返回0
int Index_KMP(String S, String T, int pos)
{
    int i, j;
    i = pos;   // i用来表示主串S当前位置的下标值
    j = 1;     // j用来表示字串T当前位置的下标值
    int next[255];
    get_next(T, next);  // 对字串T做分析,求出T的next数组
    while (i <= S[0] && j <= T[0]) {     // 当i小于S的长度 且 j小于T的长度时,循环继续
        if (j == 0 || S[i] == T[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];        // j退回到合适的位置,i值不变
        }
    }
    if (j > T[0])  return i - T[0];
    else  return 0;
}

int main()
{
    String S;
    String T;

    StrAssign(S, "ababaaaba");
    StrAssign(T, "aba");

    printf("%d", Index_KMP(S, T, 4));
    
    return 0;
}

3-4.nextval数组的求解

我们现在已经知道了KMP算法的求解思想,来看这样一个例子:
假设主串S为 aaaabcde ,字串T为 aaaaax ,我们要匹配T在S中首次出现的位置,用 i 表示主串S当前字符的位置,用 j 表示字串T当前字符的位置。

首先算出T的next数组为 :

j j = 1 j = 2 j = 3 j = 4 j = 5 j = 6
next[j] 0 1 2 3 4 5

当 i = 5 ,j = 5 时,S[5] = b , T[5] = a,不相等。按照刚才KMP的思路,此时应让j = next[j] = next[5] = 4, 也就是让j回溯到4,再与S[5]进行比较,发现又不等,j回溯到3,还是不等,j回溯到2, 还是不等,j回溯到1,还是不等。此时 i++,i 变成 6 ,再与 j = 1 开始比较。我们发现因为字串T的第1到5位都是相等的,当第T[5]与S[5]不相等时,T[4]、T[3]、T[2]、T[1]也必然与S[5]不相等,这里的比较也是多余的操作。我们对求next数组的函数进行优化,将新的值存在nextval数组中。

优化的思路是:
在原来用next数组进行回溯时,如果回溯位置t1的字符与原字符相等,那么直接回溯到t1的next数组的值t2,若t2位置的字符与原字符也相等,则继续回溯到t2的next数组的值t3,直到该字符与原字符不相等。

我们以串T ababaaaba为例,求它的nextval数组:

j 1 2 3 4 5 6 7 8 9
T a b a b a a a b a
next 0 1 1 2 3 4 2 2 3
nextval 0 1 0 1 0 4 2 1 0

当 j = 1 时,nextval[1] = 0;
当 j = 2 时,T[2] = b,next[2] = 1,而T[1] = a,与b不相等,所以 nextval[2] = next[2] = 1;
当 j = 3 时,T[3] = a,next[3] = 1, 因为T[1] ==T[3],所以nextval[3] = nextval[1] = 0;

当 j = 9 时,T[9] = a, next[9] = 3, 而3位置的字符也是a,所以nextval[9] = nextval[3] = 0;

3-5.nextval数组代码实例

以字符串 ababaaaba为例,程序的输出结果为 0 1 0 1 0 4 2 1 0

#include <stdio.h>
#include <string.h>

#define N 100

typedef char String[N];          // String s1  等价于   char s1[N]

int StrAssign(String T, char *chars)   // 初始化字符串
{
    T[0] = strlen(chars);
    for (int i = 1; i <= strlen(chars); i ++ ) {
        T[i] = *(chars + i - 1);
    }
    return 1;
}

// 返回字串T的nextval数组
void get_nextval(String T, int *nextval)
{
    int i, j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i++;
            j++;
            if (T[i] != T[j]) 
                nextval[i] = j;
            else 
                nextval[i] = nextval[j];
        }
        else {
            j = nextval[j];         // j值回溯
        }
    }
}

int main()
{
    String S;

    StrAssign(S, "ababaaaba");

    int nextval[100];
    get_nextval(S, nextval);
    for (int i = 1; i <= S[0]; i ++ )
        printf("%d ", nextval[i]);

    return 0;
}

改进过后的KMP算法只需将get_next函数 替换为 get_nextval函数即可。

内容参考:
《大话数据结构》程杰

上一篇:awk讲解、实例及注意事项


下一篇:BF算法模式匹配