串的模式匹配算法 - 一去二三遥

代码

何为模式匹配？

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

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

暴力算法（Brute-Force）

算法思想

BF算法跟名字一样，比较粗暴，从目标串T的的第一个字符起与模式串P的第一个字符比较。

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

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

下载.png

算法性能

此算法由于需要回溯，和每次比对的时模式串移动的步距较小，最差的情况（每次匹配到最后一位才会有失配情况）此时时间复杂度为O(m*n)(m,n分别为主串和子串的长度)。

代码实现

//模式匹配
int BF(const char* S,const char* P,int pos)
{
    int i = pos-1;
    int j = 0;
    int n = strlen(S);
    int m = strlen(P);
    while((i<n)&&(j<m))
    {
        if(S[i]==P[j])
        {
            i++;
            j++;
        }else{
        i = i - j+1;
        j = 0;
        }
    }
    if(j == m)
        return(i-m+1);
    else
        return -1;
}

KMP算法（Knuth-Morris-Pratt）

是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法，消除了BF算法中回溯问题，完成串的模式匹配。

算法思想

在BF算法中，用模式串去和目标串的某个子串比较时，如果不全部匹配，就要回溯到起始位置，然后后移。
显然，移回到前面已经比较过的位置，还是不能完全匹配。

KMP算法的思想是，设法利用这个已知信息，跳过前面已经比较过的位置，继续把它向后移，这样就提高了效率。

由此可知，KMP算法其实有两大要点：

(1) 计算跳转位置信息，这里我们称之为部分匹配表。

(2) 后移到指定位置，重新开始匹配。

首先，来看如何获得部分匹配表。

为了确定匹配不成功时，下次匹配时 j的位置，引入了next[]数组，next[j]的值表示模式串P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
这个next 数组叫做部分匹配表。

对于next[]数组的定义如下：
next[j]函数表.png

对于BF算法中的例子，模式串P=“abcac”，根剧next[j]的定义，可得到下表：
匹配表.png
有了部分匹配表，就可以后移到指定位置

在匹配过程中，若发生不匹配的情况。
如果next[j] >= 0，则目标串的指针 i 不变，将模式串的指针 j 移动到 next[j] 的位置继续进行匹配；

若next[j] = -1，则将 i 右移1位，并将 j 置0，继续进行比较。
下载 (1).png

算法性能

在KMP算法中求next数组的时间复杂度为O(m)，在后面的匹配中因目标串T的下标不用回溯，所以比较次数可记为n。

由此，得出KMP算法的总的时间复杂度为O(n+m)。

代码实现

//KMP算法
int Kmp(const char* S,const char* P,int pos)
{
    int i = pos-1;
    int j = 0;
    int next[100];
    Getnext(P,next);
    int n = strlen(S);
    int m = strlen(P);
    while((i<n)&&(j<m))
    {
        if(j == -1 || S[i]==P[j])
        {
            i++;
            j++;
        }else{
        j = next[j];
        //printf("%d\n",j);
        }
    }
    if(j == m)
        return(i-m+1);
    else
        return -1;
}
//构建部分匹配表
void Getnext(char* p,int next[])
{
    int l= strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < l - 1)
    {
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            if (p[j] != p[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
        {
            k = next[k];
            //printf("j£º%d\n",j);
            //printf("next[j]:%d\n",next[j]);
        }
    }
}

2018-01-14 13:08:53 星期日

本文由一去二三遥创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Feb 7, 2020 at 07:23 pm