字符串匹配:有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

一、strstr()函数
strstr() 函数搜索一个字符串在另一个字符串中的第一次出现。找到所搜索的字符串,则该函数返回第一次匹配的字符串的地址;如果未找到所搜索的字符串,则返回NULL。
strstr(const char *s1,const char *s2)函数从串s1首部开始逐个比较s2,并判断是否为s1的子串,算法复杂度为O(mn)。

一种实现方式:

char* substr(const char *str,const char *substr)
{
    int m=strlen(str);
    int n=strlen(substr);
    if(m<n)
        return NULL;
    else
    {
        for(int i=0;i<=m-n;i++)
        {
            int k=i,j=0;
            while(str[k++]==substr[j++] && k<m && j<n);
            if(j==n)
                return (char*)(str+i);
        }
        return NULL;
    }
}

二、KMP字符串匹配
strstr()函数实现了简单的字符串匹配,时间复杂度为O(mn),KMP算法具有更优的效率——O(m+n)。
简单匹配方法是逐个对比主串中的字符,每当匹配失败后,再重头开始,所以过去比较过的字符,下次依然有比较的可能性;KMP算法正是从这方面入手。比如下图:
bg2013050107.png

最后一个字符D匹配失败后,按照常理主串首个匹配字符从A->B,进行下一轮比较;事实上经过上一轮比较之后,我们已经知道D之前的六个字符“ABCDAB”,KMP的思想是设法利用这个一直信息,不要将搜索位置移到已经比较过的位置,继续后移一段距离后比较,比如上图搜索位置可以移到“AB AB...”处。

实现KMP算法首先需要构造搜索词(子串)的部分匹配表
bg2013050109.png

根据上表确定下次搜索移动位数:

移动位数=已匹配的字符数-对应的部分匹配值(最后一位匹配)

比如文本串移动次数=6-2=4,即模式串定位到从位置2开始向后比较(具体实现时,调整模式串位置为next[]数组对应值)。

到了这里大家应该知道KMP算法的核心是部分匹配表的生成,首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,
(1)“A”前缀后缀为空,共有元素长度为0;
(2)“AB” 前缀A,后缀B,共有元素长度为0;
(3)“ABC”前缀A,AB,后缀C,BC,共有元素长度为0;
(4)“ABCD”前缀A,AB,ABC,后缀BCD,CD,D,共有元素长度为0;
(5)“ABCDA”前缀A, AB, ABC, ABCD,后缀BCDA, CDA, DA, A,共有元素长度为1;
(6)"ABCDAB"的前缀为A, AB, ABC, ABCD, ABCDA,后缀为BCDAB, CDAB, DAB, AB, B,共有元素为"AB",长度为2;
(7)"ABCDABD"的前缀为A, AB, ABC, ABCD, ABCDA, ABCDAB,后缀为BCDABD, CDABD, DABD, ABD, BD, D,共有元素的长度为0

注:本文部分内容来自阮一峰的博客

标签: 字符串, 匹配, KMP

评论已关闭