串的模式匹配算法

2014/05/2220:12:53 1

一.朴素模式匹配算法

int strsub(const char* par, const char* sub, int pos)

   算法的基本思想:从主串par的第pos字符开始和子串sub的第一个字符比较,若相等,则继续捉个比较后续字符,否则则从主串的下一个字符起在重新和子串sub起始字符开始比较。以此类推,直至主串par中每个字符和子串sub的连续序列相等,则匹配相等,返回子串sub在主串par中的序号。否则匹配不成功,返回-1.下面是一个算法的实现

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

/* --------------------------------------------------------------------------*/
/** 
 * @brief  从主串中的指定位置查找指定的子串是否存在
 * 
 * @param par 主串
 * @param sub 子串
 * @param pos 从主串中的指定位置
 * 
 * @returns 如果存在返回在主串中的位置,不存在返回-1
 */
/* ----------------------------------------------------------------------------*/
int strsub(const char* par, const char* sub, int pos)
{
    /* i为主串当前位置的指针,j为子串当前位置的指针 */
    int i = pos, j = 0;
    int par_len = strlen(par);
    int sub_len = strlen(sub);
    int ret = -1;

    while (i < par_len && j < sub_len)
    {
        if (par[i] == sub[j])
        {
            /* 当主串和子串当前字符相等时,指针前移 */
            i++;
            j++;
        } else 
        {
            /* 当有元素不相等时,则主串回退,子串从头开始 */
            i = i - j + 1;
            j = 0;
        }
    }

    /* 如果所有的子串都能够匹配 */
    if (j == sub_len)
    {
        ret = i - j;        
    }

    return ret;
}

int main(int argc, char *argv[])
{
    int ret = strsub("abcdefg", "cde", 0);

    printf("ret = %d\n", ret);

    return 0;
}

   

  朴素模式匹配算法简单,但是如果碰到碰到某些极端的情况时间负责度为O(m*n),假设主串长度为m,子串长度为n,下面是是一个极端的例子:

par: ababababc
sub: abc

while循环的次数为7 * 3 ((m-n) * n)次,由此可以看出,当主串中存在多个部分匹配时,查找的效率是非常低的。

二。KMP算法

   20140523_1

我们来看上面的那张图,如果按照我们上面的朴素模式匹配算法的话,当par[2] != sub[2]时,i的值应该回溯,i的值应该从1开始,但是你看我们图中,第二趟匹配的时候i没有从1开始,而是从2开始的。第三趟也是如此,保持上次匹配i的值不变。这就是我们下面介绍的kmp算法,每当一趟匹配过程中出现字符比较不相等是,不需回溯i指针,而是利用已经得到的"部分匹配",的结果将子串向右”滑动“尽可能远的一段距离,继续进行比较.

现在我们来讨论一般的情况,假设主串用‘p0p1....pm'来表示,子串用’s0s1....sn'来表示,从上例的分析可知,为了实现改进算法,需要解决如下问题:当匹配过程中产生”失配“(既pi != sj)时,子串”向右滑动“可行的距离多远,换句话说,当主串中第i个字符与子串中第j个字符不相等时,主串中的第i个字符(i指针不回溯)应与子串中的哪个字符在比较.

假设此时应与子串中的第k个字符继续比较,则子串中前k-1个字符的必然要满足下列的关系式:

's0s1....s(k-1)' = 'p(i-k)p(i-k+1)....p(i-1)'          1式

而已经得到的”部分匹配“的结果是

's(j-k)s(j-k+1)....s(j-1)' = 'p(i-k)p(i-k+1)....p(i-1)'   2式

由1式和2式可得到下列等式

's0s1....s(k-1)' = 's(j-k)s(j-k+1)....s(j-1)'             3式

若子串串中存在满足3式的两个子串,则当匹配过程中,主串(par)中的第i字符与子串(sub)中的第j个字符比较不相等时,仅需将子串(sub)向右滑动至子串中第k+1(其标号为k)个字符和主串(par)中的第i个字符对齐。此时,子串(sub)中头k个字符必定与主串(par)中第i个字符前的k个字符相等,由上面的推论得出。由此,匹配仅需从子串(sub)中第k+1(其标号为k)个字符与主串(par)第i个字符比较起继续执行.

若令next[j] = k,则next[j]表明当子串(sub)中第j个字符与主串(par)中相应字符失配,在子串(sub)中重新和主串(par)中该字符进行比较的字符的位置。由此可引出子串的next函数的定义.

20140523_2

由此定义可推导出下列字符串的next函数值

20140523_3

kmp算法是在已知字符串的next函数值的基础上执行的,那么,如何求得字符串的next函数值了。由上述讨论可见,此函数值仅取决于字符串本身而和相匹配的主串无关,我们可以定义出发用递推的方法求得next函数值

由定义可以   next[0] = -1;

设next[j] = k, 这表明在子串中存在下列关系:

's0....s(k-1)' = 's(j-k)....s(j-1)'

其中k为满足0 < k < j的某个值,此时next[j+1] = ?可能有两种情况:

(1)若s(k) = s(j), 则表明在子串中,存在

                     's0....s(k-1)s(k)' = 's(j-k)....s(j-1)s(j)'

                     这就是说next[j+1] = k + 1, 既next[j+1] = next[j] + 1;

(2)若s(k) != s(j), 则表明

                  's0....s(k-1)s(k)' != 's(j-k)....s(j-1)s(j)'

        此时可把求next函数值的问题看成是一个模式匹配的问题,整个模式串既是主串又是子串,而当前在匹配的过程中,已有s0 = s(j-k), s1 = s(j-k+1), ...., s(k-1) = s(j-1),则当s(j) != s(k)时,应将子串向右滑动至next[k]个字符和主串中的第j个字符相比较.若next[k] = k', 且p(j) = p(k'), 则说明有以下等式

                 ‘s0....s(k'-1) = 's(j-k')....s(j-1)'

                这就是说next[j+1] = k' + 1 既 next[j+1] = next[k] + 1;

好了是时候给出kmp算法了:

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

void get_next(const char* sub, int* next)
{
    int j = 0;
    int k = -1;
    int sub_len = strlen(sub);
    next[0] = -1;

    while (j < sub_len - 1)
    {
        /* 这里的sub[j]相当于主串,sub[k]相当于子串 */
        if (k == -1 || sub[j] == sub[k])
        {
            j++;
            k++;
            next[j] = k; 
        } else 
        {
            k = next[k];
        }
    }
}

int strsub_kmp(const char* par, const char* sub, int pos)
{
    /* i为主串当前位置的指针,j为子串当前位置的指针 */
    int i = pos, j = 0;
    int par_len = strlen(par);
    int sub_len = strlen(sub);
    int ret = -1;

    /* 辅助空间 */
    int* next = (int*)malloc(sizeof(int) * sub_len);

    get_next(sub, next);

    while (i < par_len && j < sub_len)
    {
        /* j = -1的情况,就是由于par[i] != sub[0]引起,j的值已经回到0,不能再回,所以在下面执行i++,将主串的索引加1 */
        if (j == -1 || par[i] == sub[j])
        {
            i++;
            j++;
        } else 
        {
            j = next[j];
        }
    }

    /* 如果所有的子串都能够匹配 */
    if (j == sub_len)
    {
        ret = i - j;        
    }

    free(next);

    return ret;
}

int main(int argc, char *argv[])
{
    int ret = strsub_kmp("abcdefg", "cde", 0);

    printf("ret = %d\n", ret);

    return 0;
}

kmp算法的时间负责度为O(m+n), kmp算法适用于当主串中有多个部分匹配时会非常高效。

 

前面定义的next函数在某些情况下尚有缺陷,列如子串'aaaab'在和主串'aaabaaaab'匹配时, 当i = 3, j = 3时, 出现不匹配的情况,有next[j]的指示还需进行i = 3, j = 2; i = 3, j = 1; i = 3, j = 0这3次比较和第4(标号为3)个字符都相等,因此不需要再和主串的第4个字符相比较,而可以将子串一气向右滑动4个字符的位置直接进行i = 4, j = 0时的字符比较,这就是说,若按上述定义得到的next[j] = k, 而子串中s(j) = s(k),则当主串中字符p(i)和s(j)比较不相等时,不需要再和s(k)进行比较,而直接和p(next[k])进行比较,换句话说,此时的next[j]应和next[k]相同,下面是改进的get_next函数:

void get_next(const char* sub, int* next)
{
    int j = 0;
    int k = -1;
    int sub_len = strlen(sub);
    next[0] = -1;

    while (j < sub_len - 1)
    {
        if (k == -1 || sub[j] == sub[k])
        {
            j++;
            k++;
            if (sub[j] != sub[k])
            {
                next[j] = k; 
            } else 
            {
                next[j] = next[k];
            }
        } else 
        {
            k = next[k];
        }
    }
}

上面的算法描述参考严蔚敏的数据结构,详细的解析请看此书!

  • 微信扫码赞助
  • weinxin
  • 支付宝赞助
  • weinxin

发表评论

您必须才能发表评论!

目前评论:1   其中:访客  0   博主  0   引用   1

    来自外部的引用: 1

    • bill