字符串匹配【永利集团304com】,字符串匹配算法

转载请注明出处:

模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配

经常遇到的一个任务是在一段文字中定位一个词,类似地操作有,在一个字符串中定位一个子串的位置,这通常被称为字符串的模式匹配,以下简称字符串匹配

假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这个问题成为模式匹配问题。P称为模式,T称为目标。如果T中存在一个或多个模式为P的子串,就给出该子串在T中的位置,称为匹配成功;否则匹配失败。

那么,字符串匹配是什么?比如说,有一个字符串S=”BBCD ABCDAB ABCDABCDABDAB“,其中是否包含另一个字符串T=”ABCDABD“?如果有,子串T位于主串S中什么位置(可用T首字母在S中所在位置表示)。

蛮力算法(BF算法)

本文主要介绍两种常用算法,朴素匹配算法KMP算法及其改进版。KMP算法全称是Knuth–Morris–Pratt算法[1],它以三个发明者命名
——
D.E.Knuth、J.H.Morris和V.R.Pratt。第一个K就是大名鼎鼎的图灵奖获得者Donald
E.
Knuth,他是广为流传的《计算机程序设计艺术》系列的作者。不过,还有一个小八卦,他作为一名计算机科学家写自己著作的时候觉得当时世界上的排版系统太渣,于是暂放下写书工作,一举发明计算机排版系统TEX。总感觉像世外高人,冷不丁告诉世人他又练成了另一门绝世武功。我想现在很多用LaTex排版论文书籍的科技同仁们都知道他吧。

算法思想

目标串T的的第一个字符起与模式串P的第一个字符比较。

若相等,则继续对字符进行后续的比较;否则目标串从第二个字符起与模式串的第一个字符重新比较。

直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。

永利集团304com 1

OK,言归正传,下面先介绍朴素匹配算法吧~

算法性能

假设模式串的长度为m,目标串的长度为n:N为外循环,M为内循环。

BF算法存在回溯,严重影响到效率,最坏的情况的是N*M,所以算法的复杂度为O(mn).暴力算法中无法利用已知的信息,也就是模式串的信息,减少匹配。比如在第四步中,t[5]和p[4]不匹配,然后又回溯(图有点问题),t[3]和P[0]肯定不同,因为之前匹配过了,我们得知t[3]=p[1],而p[0]和p[1]不同。

索引定义

首先定义主串S和子串T的匹配索引ij

String S: | B | B | C | D | | A | B | C | D | ... Index i: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...

String T: | A | B | C | D | A | B | D |Index j: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 

代码

永利集团304com 2永利集团304com 3

int bf(const char *text, const char *find)
{
    //异常判断
    if (*text == '/0' || *find == '/0')
    {
        return -1;
    }

    int find_len = strlen(find);
    int text_len = strlen(text);
    if (text_len < find_len)
    {
        return -1;
    }
    //去除const属性
    char *s =const_cast<char*>(text);
    char *p = s;
    char *q = const_cast<char*>(find);
   //执行BF算法
    while (*p != '')
    {
        //匹配成功,指针前移
        if (*p == *q)
        {
            p++;
            q++;
        }
        //否则,回溯,通过记录之前的指针位置,重新赋值。
        else
        {
            //s++,p指向回溯的位置.
            s++;
            p = s;
            //q重新指向初始位置
            q =const_cast<char*>(find);
        }
        //执行成功了,返回位置。
        if (*q == '')
        {
            return (p - text) - (q - find);
        }
    }
    return -1;
}

暴力算法

 

算法原理

最直接也是最暴力的思路就是 ——
按顺序依次比较子串T中字符和主串S中字符。如果不一致就后移子串T,直至找出主串S中子串T,或子串T已移出主串S范围。

示例如下:

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

1 –
首先,比较子串T的第一个字符与主串S的第一个字符,发现匹配失败,所以子串T后移一位。

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

2 –
发现仍匹配失败,所以子串T继续后移,直至子串T与主串S的第一个字符成功匹配。

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

3 – 接着依次比较第二个字符,匹配成功,继续比较下一位字符。

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

4 – 直至又有字符不匹配为止。

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

5 – 此时最直接的做法自然是,将子串T整个后移一位,再依次逐个比较。

S: BBCD ABCDAB ABCDABCDABDAB |T: ABCDABD

这就是朴素匹配算法。虽然可行,但时间复杂度很高,因为要把搜索位置移到已经比较过的位置,重新比较一遍,即索引i的回溯

在下面算法实现中可以清楚看到,索引i索引j的回溯索引j的回溯是不可避免的,因为要确认匹配子串T中的每一个字符。那么,问题来了。。。

Q:能不能尽量避免索引i的回溯呢?

A:请见KMP算法。

KMP算法

Knuth-Morris-Pratt算法(简称KMP),是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法,消除了BF算法中回溯问题,完成串的模式匹配。KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。

时间复杂度

  • 最好的情况是开始就匹配成功,则时间复杂度为O
  • 次好的情况只要首字符匹配上就完全匹配成功,则时间复杂度为O。其中,n为主串S长度,m为子串T长度。
  • 最坏的情况是最终没有可匹配的字符串:在主串S每一个字符处都比较一遍子串T的每一个字符。此时,时间复杂度为O*m)

算法思想

永利集团304com 4

在上图中,在S=”ababcabcacbaa”中查找T=”abcac”,如果使用KMP匹配算法,当第一次搜索到S[2]
和T[2]不等后,S下标不是回溯到1,第二次发生不匹配时,S下标也不是回溯到开始,T的下标不是回溯到开始,而是根据T中T[4]==’b’的模式函数。

关键思想:在匹配过程中,若发生不匹配的情况。

如果next[j] >=
0,则目标串的指针 i 不变,将模式串的指针 j 移动到 next[j]
的位置继续进行匹配;

若next[j] =
-1,则将 i 右移1位,并将 j 置0,继续进行比较。

程序算法思路:

如果j =
-1,或者当前字符匹配成功(即S[i] ==
P[j]),都令i++,j++,继续匹配下一个字符;

如果j !=
-1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j =
next[j]。此举意味着失配时,模式串P从开始位置移动next[j],然后开始匹配。

发表评论

电子邮件地址不会被公开。 必填项已用*标注