精华内容
下载资源
问答
  • 串的模式匹配算法

    2015-10-11 09:37:10
    模式匹配成功是指在目标s中找到一个模式t;不成功则指目标s中不存在模式t。 以下算法假设采用顺序存储结构,即: #define MAXSIZE 50typedef struct{ char data[MAXSIZ
    设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t;不成功则指目标串s中不存在模式串t。
    以下算法假设串采用顺序存储结构,即:
    1. #define MAXSIZE 50
    2. typedef struct
    3. {
    4.     char data[MAXSIZE];
    5.     int length;
    6. }SqString;
    Brute-Force算法
        Brute-Force算法简称为BF算法,亦称为简单匹配算法,其基本思路是:从目标串s的第一个字符开始和模式串t中的第一个字符比较,若相等,则继续逐个比较后续的字符;否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。以此类推,若从模式串t的第i个字符开始,每个字符依次和目标串s中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,算法返回-1 。
    该算法C实现代码如下:
    1. int BFIndex(SqString *sp, SqString *tp)
    2. {
    3.     int i, j;
    4.     if(sp->length >= tp->length)
    5.     {
    6.         for(i = 0; i < sp->length; i++)
    7.         {
    8.             for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);
    9.             if(j == tp->length) return(i);
    10.         }
    11.     }
    12.     return(-1);
    13. }
    该算法的时间复杂度分析:
           假设目标串s的长度为m,模式串t的长度为n。第一个for循环的语句频度为m,第二个for循环的语句频度为n,故该算法的时间复杂度为O(mn),当然这是最坏的情况。该算法在最好情况下的时间复杂度为O(n)。
           该算法比较简单,易于理解,但效率不高,主要原因是:主串指针在若干字符序列比较相等后,若有一个字符比较不相等,需要回溯(主串指针的变化 i -> i+j -> i,回溯体现在i+j -> i这个过程,因为主串指针在第一个for循环每次执行i++时,都由i+j变为i,当然i+j >= i)。
    例程:
    1. /*
    2. * file: Brute-Force.c
    3. * author: Jesse
    4. * date: 2011/08/07 13:15
    5. */
    6. #include <stdio.h>
    7. #define MAXSIZE 50
    8. typedef struct
    9. {
    10.     char data[MAXSIZE];
    11.     int length;
    12. }SqString;
    13. int BFIndex(SqString *sp, SqString *tp)
    14. {
    15.     int i, j;
    16.     if(sp->length >= tp->length)
    17.     {
    18.         for(i = 0; i < sp->length; i++)
    19.         {
    20.             for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);
    21.             if(j == tp->length) return(i);
    22.         }
    23.     }
    24.     return(-1);
    25. }
    26. int main(void)
    27. {
    28.     SqString s, t;
    29.     int index;
    30.     printf("\n请输入目标串s和它的长度,以空格隔开,以回车键结束整个输入:\n");
    31.     scanf("%s %d", s.data, &s.length);
    32.     printf("请输入模式串t和它的长度,以空格隔开,以回车键结束整个输入:\n");
    33.     scanf("%s %d", t.data, &t.length);
    34.     index = BFIndex(&s, &t);
    35.     if(-1 == index) printf("\n匹配失败!\n");
    36.     else printf("\n匹配成功! i = %d\n", index);
    37.     return(0);
    38. }
    展开全文
  • 串的模式匹配算法——KMP

    千次阅读 2013-04-18 17:57:47
    声明 ... 原文“text”翻译为主,通常用S表示,长度为n; 原文"pattern"翻译为模式串,通常用T表示,长度为m;...在移动了模式串之后,原始的算法(应该就是普通BF吧~)忽略了之前匹配的信息,

    声明

    原文链接:http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm ;
    原文的“text”翻译为主串,通常用S表示,长度为n;
    原文的"pattern"翻译为模式串,通常用T表示,长度为m;
    括号中是自己的一些注释;

    思想

    在移动了模式串之后,原始的算法(应该就是指普通的BF吧~)忽略了之前匹配的信息,所以可能造成主串一遍又一遍的回溯,最坏情况下的复杂度为Θ(nm) 。
    KMP算法利用了从之前的匹配中获得的信息,它不会重复比较匹配过的主串(也就是S的指针永远不会回溯),所以它的复杂度为O(n)。
    无论如何,分析模式串的结构是非常必要的。这个过程的复杂度是O(m),而 m<=n ,所以整个算法的复杂度为O(n)。

    基本定义

    定义:
    (前缀后缀不再罗嗦了。。就是不包括同 x 串完全相等的,翻译为真前缀和真后缀)
    x串的border(不知道怎么翻译,保留),是这样一个子串r,使得r  =  x0 ... xb-1并且  r  =  xk-b ... xk-1   b element {0, ..., k-1} (其实就是串 x 的前面一部分和后面一部分是相等的,相等部分的子串的长度是b,想想为什么定义这个border,很好的思想哦~这样主串的指针就不必回溯了~后面会说明~)
    x串的border即是真前缀,也是真后缀,我们将b称为x的border的长度。

    比如:
    让 x = “abacab”
    真前缀:ε, a, ab, aba, abac, abaca
    真后缀:ε, b, ab, cab, acab, bacab
    border:ε(长度是0), ab(长度是2)

    空串 ε 总是x的border,而它自己没有border。

    下面的例子说明了KMP算法是怎样根据一个串的border来决定移动的距离的。(说是移动的距离,体现在程序中,其实就是模式串的指针 j 要向前怎么移动才能保证主串S的指针不回溯就能继续判断匹配)

    例子:
    0 1 2 3 4 5 6 7 8 9 ...
    a b c a b c a b d
    a b c a b d
              a b c a b d

    可以看出0到4都匹配了,5没有匹配,模式串可以移动三个位置(即不必判断模式串的前两位,指针 j 移动到第三位 c 的位置),主串的位置仍然保留在5。
    移动的距离是根据最长匹配的前缀得到的,是该前缀的border长度的最大值。在这个例子中,最长匹配前缀是abcab,它的长度是 j = 5.他最长的border是ab,长度是2,所以移动的距离是 j - b = 5 - 2 = 3.
    在这个过程中,每个模式串的前缀的最长的border值都可以得到。然后在查找的过程中,移动距离就可以根据匹配的前缀计算出来了。

    过程

    理论: 让r, s作为串 x 的border,并且满足|r| < |s|,那么r一定是s的border.
    证明:下图 展示了r,s作为两个border 的串 x 。r是x的前缀,也是真前缀,因为它比s短。而r也是x的后缀,因此,也是s的真后缀。所以r是串s的border。
                                                 Borders r, s of a string x
    定义:
    让 x 作为一个串, a 作为一个字母,如果ra是xa的border,那么x的border就可以从 r 扩展到 ra(过程算法的理论依据哦~称为T1.1)。
    下图展示了这个过程:
                                                                               Extension of a border

    在这个过程中,一个m+1为长度的数组会被计算出来。b[i]表示模式串(i = 0, ..., m)中长度为i的前缀的最长border的长度。由于空的前缀没有border,所以我们将b[0] 置为-1。下图是拥有长度为b[i]的border的模式串的前缀。

                                                                             Prefix of length i of the pattern with border of width b[i]

    假设b[0], ..., b[i] 的值都是已知的,b[i+1] 的值可以通过检查前缀p0 ... pi-1 的border是否可以由pi扩展。这就是 pb[i] = pi 的情况,如上图。那么borders就可以通过前面 b[i], b[b[i]] 等等的值计算出来。
    这个过程算法包含一个 j 的循环。如果pj = pi 的话,长度为 j 的border又可以被 pi 扩展,否则pj <> pi的话,下一个最长的border 就能通过让 j = b[j] 获得。这个循环结束的条件是没有border可以被扩展(j = -1)。在 j++语句之后,这个值就被写入b[i+1]。
    (也就是说,根据T1.1,如果pj = pi,扩展后b[i+1] 的值就是b[i] 的值+1即可;但如果不相等的话,令j = b[j] ,再判断新的 pj 与 pi 是否相等,依此类推,也就是程序中的while循环!因为不相等时,border的长度肯定更短,而b[j] 就是前缀p0, p1,...,pj-1的border,因为前后部分一样,下面在此判断pi 和 pj 是否相等又是在重复前面的过程,如果相等还是根据T1.1加一得到b[i+1]的值,这点不太好想,有点递归的赶脚。。)
    过程算法:
    void kmpPreprocess()
    {
        int i=0, j=-1;
        b[i]=j;
        while (i<m)
        {
            while (j>=0 && p[i]!=p[j]) j=b[j];
            i++; j++;
            b[i]=j;
        }
    }

    例如:
    对于模式串 p = ababaa,数组b中的border的长度有下面的值。比如我们有 b[5] = 3,因为长度为5的前缀 ababa 拥有长度为3的border.                                                                                                                                                                             

    查找算法

    上面的过程算法可以被应用到串pt 上来。如果只有最长的borders被计算出来,那么pt 的前缀的长度为m的border会匹配模式串 t ,假设border不是自我重叠的,如下图所示:
                                                                                    Border of length m of a prefix x of pt
    这解释了过程算法和下面的查找算法的相似之处。
    查找算法:
    void kmpSearch()
    {
        int i=0, j=0;
        while (i<n)
        {
            while (j>=0 && t[i]!=p[j]) j=b[j];
            i++; j++;
            if (j==m)
            {
                report(i-j);
                j=b[j];
            }
        }
    }
    在内层循环中,在 j 处不匹配的时候,匹配模式串的前缀中最长的border会被考虑,如下图:
                                                            Shift of the pattern when a mismatch at position j occurs
    继续在b[j]处比较,border的长度会导致模式串的移动。如果发生不匹配的情况,考虑下一个最长border,以此类推,直到没有剩下的border,即j = -1 或者下一个符号匹配了。然后我们就有了新的模式串的匹配前缀,可以继续进行外层循环了。

    如果模式串的所有m个符号都和主串匹配完毕,即j = m,会调用一个函数来返回匹配的位置i-j。然后,模式串会在最长border允许的范围内尽可能多的移动。

    下面的例子演示了查找算法,绿色代表匹配,红色代表不匹配。

    例子:

                                                                                      

    分析

    过程算法内层的 while 循环将 j 的值减少到至少为1,因为b[j] < j. 循环在 j = -1的时候停止,因此,它最多是和 j++ 的次数相等。由于j++ 在外层循环中执行了m次,所以内层循环的整体次数最多是m,所以过程算法需要O(m) 步。
    相似的查找算法需要O(n)步。上面的例子展示了这个“阶梯状的图”的宽度至少和高度相等(因为每次不匹配都会移动,最极端的情况是每一次都移动1,此时宽度和高度相同),因为最多有2n次比较。
    所以KMP算法的复杂度为O(n).

    其他模式值

    其实next 函数也有其他的定义,但思想都是利用前面的比较来消除回溯提高效率,参考链接 : http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
    展开全文
  • KMP匹配算法的重点在于利用模式串自身的重复部分,在匹配中消除那些重复的匹配过程。 下面约定 字符串和next数组的下标从1开始(人为规定) i为指向主串的指针,j和k为指向模式串的指针 T代表为模式串数组,S

    这里先给出之前我参考的博客网址,以及参考的书籍是数据结构(严蔚敏)。

    参考代码的网址

    这里我总结一下我的思路。

    先介绍一些基本概念

    1. 主串:这里指的是要匹配的字符串
    2. 模式串:需要在主串中寻找的字符串
    3. KMP匹配算法的重点在于利用模式串自身的重复部分,在匹配中消除那些重复的匹配过程。

    下面约定

    1. 字符串和next数组的下标从1开始(人为规定)
    2. i为指向主串的指针,j和k为指向模式串的指针
    3. T代表为模式串数组,S代表主串数组
    4. ==表示左右相等,!=表示左右不相等

    next数组的求解

    1. next[1] = 0

    我们约定next数组的第一个位置值为0,代表的是模式串的第一个字符失配(也就是连第一个字符都不匹配),这时就从主串当前失配字符的下一个字符开始重新匹配(i增1),模式串当然也是从头开始(j为1)。

    1. 已知next[j] = k

    所以:’T[1]…T[k-1]’ == ‘T[j-k+1]…T[j-1]’

    这里解释一下:上面的表示模式串的前缀长度为k-1的字符串和从j往前数k-1长度的字符串是相等的。

    这时会出现两种情况:

    第一种:T[k] == T[j]

    所以:’T[1]…T[k]’ == ‘T[j-k+1]…T[j]’
    因为:’T[1]…T[k-1]’ == ‘T[j-k+1]…T[j-1]’的时候next[j] = k
    所以:’T[1]…T[k]’ == ‘T[j-k+1]…T[j]’的时候next[j+1] = k+1 = next[j] + 1

    这里会出现一个问题:如果S[i] != T[j],模式串的第j个字符失配,那么我们就会让S[i]和T[next[j]]进行比较,但是我们这里是第一种情况T[next[j]] == T[j],所以当然也不等于S[i],这就等于做了一次无用功。

    所以需要在上面的判断里面再加上一个判断,若T[k+1] == T[j+1],则next[j+1] = next[k+1],否则next[j+1] = k+1

    这里举个例子:模式串ABAB,当k指向第一个位置A,j指向第三个位置A,它们俩相等,原本直接赋值next[j+1] = 2但是因为T[k+1] = T[j+1],所以改成next[j+1] = next[k+1] = 1。原本ABAB的next数组为0112,现在变为0101。

    第二种:T[k] != T[j]

    举个例子:模式串abacdababc,其中k为4,j为9。分别截取出来看就是abac和abab

    因为:T[k] != T[j],可以看出abac的前面的a和abab的倒数第二个a相同,就直接就可以从abac的第二个b开始进行比较
    所以:这里只需将k改为2也就是k = next[k],让abac第2个和abab最后一个元素对其即可。再次和T[k]比较,若相同则T[j+1] = next[k]+1;否则,再次执行j = next[j]直到j = next[1] = 0为止,这样T[j+1] = next[1]+1 = 1

    总结一下就是:

    1. T[1]…T[k]’ == ‘T[j-k+1]…T[j],next[j] = k;
    2. 在1的条件下
      1. T[k]==T[j]且T[k+1] == T[j+1],next[j+1] = next[k+1]
      2. T[k]==T[j]且T[k+1] != T[j+1],next[j+1] = k+1
      3. T[k]!=T[j],k = next[k]
    3. next[1] = 0

    因为这些都是推出来的,就像数学的定理,可以因为所以的一步步推出来,所以当成公式或者转化成图像记忆都可以。

    综合上述分析,程序思路就可以得出

    1. 将j置为1指向模式串的第一个元素,k为0表示从模式串第一个开始比较,next数组第一位为0
    2. 接下来当然就是一个循环遍历整个模式串
      1. 两个判断条件k是否为0以及T[k]是否等于T[j],若k为0表示又从头开始匹配,则直接将k和j增1,。若T[k]等于T[j]且T[k+1] == T[j+1],表示next[j+1] = next[k+1],若不等于,就按照正常的方法next[j+1] = k+1
        1. 每一次的判断都是为了求得next[j+1]的值,所以这里j需要增1,k增1前面已经讲过了
      2. 否则就是k = next[k]的情况

    下面给出改进前和改进后的c语言代码

    改进前的代码

    void get_next(SString T, int next[]){
        int j = 1;
        int k = 0;
        next[1] = 0;
    
        while(j<T[0]){
            if(k==0 || T[j]==T[i]){
                j++;
                k++;
                next[j] = k;
            }else{
                k = next[k];
            }
        }
    
        return;
    }

    改进后的

    void get_nextval(SString T, int nextval[]){
        int j = 1;
        int k = 0;
        next[1] = 0;
    
        while(j<T[0]){
            if(k==0 || T[k]==T[j]){
                j++;
                k++;
                if(T[k]!=T[j]){
                    nextval[j] = k;
                }else{
                    nextval[j] = nextval[k];
                }
            }else{
                k = next[k];
            }
        }
    
        return;
    }
    展开全文
  • 模式匹配成功是指在目标s中找到一个模式t; 不成功则指目标s中不存在模式t Brute-Force算法 采用穷举思路,从目标s第一个字符开始和模式t第一个字符开始比较 若相等,则继续逐个比较后续字符 不...

    设有主串s和子串t,子串t的定位就是要在主串中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称为模式匹配

    模式匹配成功是指在目标串s中找到一个模式串t;
    不成功则指目标串s中不存在模式串t

    Brute-Force算法

    采用穷举的思路,从目标串s的第一个字符开始和模式串t的第一个字符开始比较

    • 若相等,则继续逐个比较后续字符
    • 不相等则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较

    若匹配成功则返回主串中第一次出现模式串的位置,匹配失败返回-1

    以目标串"abcdefgab",模式串"abcdex"为例

    在这里插入图片描述

    匹配次数 位置 结果
    第1.1次匹配 i = 0,j = 0 a = a
    1.2 i = 1,j = 1 b = b
    1.3 i = 2,j = 2 c = c
    1.4 i = 3,j = 3 d = d
    1.5 i = 4,j = 4 e = e
    1.6 i = 5,j = 5 f ≠ x
    第2次匹配 i = 1,j = 0 b ≠ a
    第3次匹配 i = 2,j = 0 c ≠ a
    第4次匹配 i = 3,j = 0 d ≠ a
    第5次匹配 i = 4,j = 0 e ≠ a
    第6次匹配 i = 5,j = 0 f ≠ a
    第7次匹配 i = 6,j = 0 g ≠ a
    第8.1次匹配 i = 7,j = 0 a = a
    8.2 i = 8,j = 1 b = b

    当i = 9时,目标串下标越界,匹配结束。
    结束时j没有指向模式串尾,说明没有匹配成功。返回-1

    BF算法的实现

    int
    BF_index( char *s1, char *s2 )
    {
    	int i = 0, j = 0;
    	int s1_len = strlen(s1);
    	int s2_len = strlen(s2);
    	while( i < s1_len  && j < s2_len ){
    		if( s1[i] == s2[j] ){
    			i++;
    			j++;
    		}else{
    			i = i - j + 1;
    			j = 0;
    		}
    	}
    	if( j >= s2_len ){
    		return ( i - s1_len );
    	}else{
    		return -1;
    	}
    }
    

    最好时间复杂度为O( s2_len )
    最坏时间复杂度为O( s1_len × s2_len )
    平均时间复杂度为O( s1_len × s2_len )

    这个算法简单易于理解,但效率不高,主要原因是:主串指针i在若干个字符序列比较相等后,若有一个字符比较不相等仍需回溯,重复做前面的事情。

    KMP算法

    引用了《大话数据结构》第5章KMP算法的内容

    KMP算法专门针对BF算法中主串指针的回溯的问题进行优化,极大的提高了模式匹配算法的效率

    例一

    以目标串S"abcdefgab",模式串T"abcdex"为例
    在这里插入图片描述
    首先,模式串T有一个特点:首字符a仅在T[0]出现,后面的字符和T[0]均不相等。

    第一次匹配的结果显示
    S[i]=T[i](i=0,1,2,3,4) S[i] = T[i]( i = 0,1, 2, 3, 4 )
    由这个结果得出,在S串中的a也只在S[0]出现,这意味着S[1]、S[2]、S[3]、S[4]都不是a,这是可以直接得出的结论,所以在BF算法中的第2, 3, 4, 5次匹配都是多余的。

    这里是KMP算法的关键。我们知道T串中首字符a与它后面的字符均不相等,然后通过判断得出T[1] = S[1],则可以省略BF算法的第2次匹配。同理,T[2]、T[3]、T[4]与S对应位置的字符判断相等后,也可以省略掉对应的匹配操作。

    第6次匹配不能省略,因为在第1.6次匹配时只得出了S[5]≠T[5],没有得出S[5] ≠ T[0],所以这一步判断S[5]和T[0]需要保留,j变为0。

    首字符仅在T[0]出现的情况比较特殊,下面讨论较一般的情况,即除了串首之外,首字符还分布在模式串不同的位置。

    例二

    以目标串abcababca,模式串abcabx为例
    在这里插入图片描述
    和例一相似,模式串T的特征是:首字符a出现的位置不唯一,分别是T[0]和T[3]

    第一次匹配结果
    S[i]=T[i](i=0,1,2,3,4) S[i] = T[i]( i = 0,1, 2, 3, 4 )

    1. T[0] ≠ T[1],省略BF算法的第2次匹配
    2. T[0] ≠ T[2],省略BF算法的第3次匹配

    T[0] = T[3],T[1] = T[4],而在第一次匹配我们已经知道T[3] = S[3],T[4] = S[4],即S[3] = T[0],S[4] = T[1]。而BF算法做多了两次匹配才得出相等的结论,显然第4次、第5次匹配是多余的。

    在BF算法中,目标串指针i是不断地往回走的,在KMP算法中i不往后走,而是让模式串T的指针j变化。

    j值的变化取决于T串中是否有重复的部分

    把T串各个位置j值的变化定义为一个数组next,那么next的长度就是T串的长度。

    模式串T中存在某个k( 0 < k < j ),使得以下等式成立
    T0T1...Tk1=TjkTjk+1...Tj1 “T_0T_1...T_{k-1}”=“T_{j-k}T_{j-k+1}...T_{j-1}”
    例如,T=ababc,当j=4时,T[ j ] = c,有T[0]T[2-1] = T[4-2]T[4-2+1],k = 2,所以next[4] = k
    = 2

    归纳起来就是
    next[j]=x={1,j=0max{k0<k<j,T0T1...Tk1=TjkTjk+1...Tj1}0 next[j] =x = \begin{cases} -1, 当j=0时\\ \max\{k | 0<k<j, 且“T_0T_1...T_{k-1}”=“T_{j-k}T_{j-k+1}...T_{j-1}”\}当此集合不为空时\\ 0其他情况 \end{cases}

    推导next数组

    T = abcdex

    j 0 1 2 3 4 5
    T[ j ] a b c d e x
    next[ j ] -1 0 0 0 0 0
    1. j = 0,next[0] = -1
    2. j = 1,0 < k < 1,下标不能是小数,属于其他情况,next[1] = 0
    3. j = 2,k = 1,此时从0到k-1只有T[0],T[0] ≠ T[1],属于其他情况,next[2] = 0
    4. j = 3,k = 1或2,当k = 2时,T[0]T[1] ≠ T[1]T[2],属于其他情况,next[3] = 0

    同理,最终得到T的next数组为-1,0,0,0,0,0

    T = abcabx

    j 0 1 2 3 4 5
    T[ j ] a b c a b x
    next[ j ] -1 0 0 0 1 2
    1. j = 0,next[0] = -1
    2. j = 1,同上说明,next[1] = 0
    3. j = 2,k = 1,同上,next[2] = 0
    4. j = 3,k = 1或2,同上,next[3] = 0
    5. j = 4,k = 1或2或3,当k = 1时,T[0] = T[3],next[4] = 1
      在后续的计算可以不用按照定义求解,从j-1出发,看能有多少个字符和T串开头匹配即可
    6. j = 5,有T[0]T[1] = T[3]T[4],得到 k = 2,next[j] = 2

    最终next数组为-1,0,0,0,1,2

    T = ababaaaba

    1. j = 0,next[0] = -1
    2. j = 1,同上,next[1] = 0
    3. j = 2,同上,next[2] = 0
    4. j = 3,有T[0] = T[2],next[3] = 1
    5. j = 4,有T[0]T[1] = T[2]T[3],next[4] = 2
    6. j = 5,有T[0]T[1]T[2] = T[2]T[3]T[4],next[5] = 3
      在这里插入图片描述
    7. j = 6,有T[0] = T[5],next[6] = 1
    8. j = 7,有T[0] = T[6],next[7] = 1
    9. j = 8,有T[0]T[1] = T[6]T[7],next[8] = 2

    next数组为-1,0,0,1,2,3,1,1,2

    T = aaaaaaaab

    1. j = 0,next[0] = -1
    2. j = 1,next[1] = 0
    3. j = 2,T[0] = T[1],next[2] = 1
    4. j = 3,取k最大的情况即T[0]T[1] = T[1]T[2],next[3] = 2
    5. j = 8,next[8] = 7

    next数组为-1,0,1,2,3,4,5,6,7

    到这里就可以解释next[j] = k的含义了,这个等式表示模式串T[j]之前已经有k个字符成功匹配,下一次应该从T[k]开始匹配,而next[j] = -1表示T串当前没有加速匹配的信息,加1,下一次从0开始判断。

    KMP算法的实现

    void
    KMP_getNext( char *s1, int *next )
    {
    	int j = 0, k = -1;
    	next[0] = -1;
    	while( j < strlen(s1) - 1 ){
    		if( k == -1 || s1[j] == s1[k] ){
    			j++;
    			k++;
    			next[j] = k;
    		}else{
    			k = next[k];
    		}
    	}
    }
    
    int
    KMP_index( char *s1, char *s2 )
    {
    	int i = 0, j = 0;
    	int next[MAXSIZE];
    	int s1_len = strlen(s1);
    	int s2_len = strlen(s2);
    	
    	KMP_getNext( s1, next );
    	while( i < s1_len && j < s2_len ){
    		if( j == -1 || s1[i] == s2[j] ){
    			i++;
    			j++;
    		}else{
    			j = next[j];
    		}
    	}
    	if( j >= s2_len ){
    		return ( i - s2_len );
    	}else{
    		return -1;
    	}
    }
    

    在这里插入图片描述

    求next数组的时间复杂度为O(s2_len),KMP算法匹配时不回溯,则整体算法时间复杂度为O( s2_len + s1_len )

    需要强调的是,KMP算法仅当T串和S串之间有许多部分匹配的情况下才体现出它的优势。

    例题

    已知字符串S为"abaabaabacacaabaabcc",模式串T为"abaabc",采用KMP算法进行匹配,第一次出现“失配”(s[i] != t[j])时,i = j = 5,则下次开始匹配时,i和j的值分别是

    题目要求采用KMP算法,主串指针不回溯,i = 5,通过推导next数组找到next[j]

    j 0 1 2 3 4 5
    T[ j ] a b a a b c
    next[ j ] -1 0 0 1 1 2

    得到next[5] = 2
    综上,i = 5, j = 2

    改进的KMP算法

    以S="aaaabcde",T="aaaaax"为例

    求出next数组为-1、0、1、2、3、4。
    在这里插入图片描述

    当 i = 4,j = 4时,S[4] ≠ T[4],于是j = next[j],得到 j = 3。S[4] ≠ T[3],j = next[j],得到 j = 2…一直回退到 j = 0,才能i++j++,得到 i = 5,j = 0

    用首位next[0]的值去代替与它相同的字符后续的next[j]的值可以省去上面回退的过程。

    推导nextval数组

    T = "ababaaaba"

    先推导出next数组:-1,0,0,1,2,3,1,1,2

    1. j = 0,nextval[0] = -1
    2. j = 1,next[1] = 0,T[1] ≠ T[0],nextval[1] = next[1] = 0,保持不动
    3. j = 2,next[2] = 0,T[2] = T[0],所以nextval[2] = nextval[0] = -1
    4. j = 3,next[3] = 1,T[3] = T[1],所以nextval[3] = nextval[1] = 0
    5. j = 4,next[4] = 2,T[4] = T[2],所以nextval[4] = nextval[2] = -1
    6. j = 5,next[5] = 3,T[5] ≠ T[3],所以nextval[5] = next[5] = 3
    7. j = 6,next[6] = 1,T[6] ≠ T[1],所以nextval[5] = next[5] = 1
    8. j = 7,next[7] = 1,T[7] = T[1],所以nextval[7] = nextval[1] = 0
    9. j = 8,next[8] = 2,T[8] = T[2],所以nextval[8] = nextval[2] = -1

    最终得到nextval数组为 -1, 0, -1, 0, -1, 3, 1, 0, -1

    T = "aaaaax"

    求出next数组为-1、0、1、2、3、4。

    1. j = 0,nextval[0] = -1
    2. j = 1,next[1] = 0,T[1] = T[0],nextval[1] = nextval[0] = -1
    3. j = 2,next[2] = 1,T[2] = T[1],nextval[2] = nextval[1] = -1
    4. j = 5,next[5] = 4,T[5] ≠ T[4],nextval[5] = next[5] = 4,保持不动

    最终求出nextval数组为 -1,-1,-1,-1,-1,4

    在这里插入图片描述

    展开全文
  •  以下介绍两种常见的模式匹配算法: Brute-Force模式匹配算法 暴风算法,又称暴力算法。  算法的核心思想如下: 设S为目标,T为模式,且不妨设: S=“s0s1s2…sn-1” , T=“t0t1t2 ...
  • 寻找字符S中字符T出现位置或者次数问题属于字符串匹配问题。 BF算法: eg: 主:s="ababcabcacbab"; 模式串:t="abc"; 1.变量i,j(初始值为0、1都行)分别指向S、T第一个位置(这里是指i=1;j=1(i=0;j=0)...
  • 在对字符串的操作中,我们经常要用到子串的查找功能,我们称子串为模式串,模式串在主串中的查找过程我们成为模式匹配,KMP算法就是一个高效的模式匹配算法。KMP算法是蛮力算法的一种改进,下面我们先来介绍蛮力算法...
  • 字符串模式匹配,找出特定的模式串在一个较长的字符串中出现的位置。 朴素的模式匹配算法 很直观的可以写出下面的代码,来找出模式串在... 3: 功能:字符串的模式匹配 4: 参数: 5: s:目标串 6: ...
  • \quad \quadBM(Boyer-Moore) 算法,一种非常高效字符串匹配算法。据实验统计,它性能著名 KMP 算法 3 到 4 倍。各种文本编辑器"查找"功能(Ctrl+F),大多采用Boyer-Moore算法 2、原理 2.1 坏字符...
  • 字符串的匹配问题在主串S中寻找一个与模式串P完全相同的子串,称为字符串模式匹配 一、逐位比较匹配–Brute Force 设计思路 以主串S的第一位字符为起点,每次与模式串P进行逐位的比较。若当前比较的字符相等...
  • 详解字符串的快速匹配算法:KMP

    千次阅读 多人点赞 2018-08-14 00:44:06
    BF 算法是指将主串的第 I 个字符与模式串的第1个字符进行比较,如果相等便继续进行比较操作;若不匹配时,回溯到主串的第 I+1 个字符继续与模式串的第1个字符进行比较,直到结果出现。 而 KMP 算法则是利用匹配失败...
  • 串的简单模式匹配和KMP算法

    千次阅读 2017-08-31 14:24:56
    串的简单模式匹配和KMP算法  所谓串就是字符串,在...其中待定位的子串称为模式串,简单模式匹配算法的思想:从主串的第一个位置和模式串的第一个字符开始比较,如果相等,则继续逐一比较后续字符;否则从主串的
  • 字符串模式匹配的BF算法与KMP算法

    千次阅读 2012-03-05 15:50:53
     传统的字符串模式匹配算法(也就是BF算法)就是对于主串和模式串双双自左向右,一个一个字符比较,如果不匹配,主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O(n*m),其中n和m分别为串s
  • 一 用next[]数组 1.求next数组的公式 (1)next[0]=-1 ...设s时目标串,t时模板串,设i指针和j指针分别目标串和模式串的正待比较的字符,另i和j的初值0。若有si=tj,则i和j分别增1;否则i不...
  • 闲话少说,我们来看下字符串的文本匹配都有哪些有趣的算法。Tips:模式匹配指有一个敏感词或者叫模式 A,对于一个输入字符串B,查找B是否含有A,且A的位置。程序员解法首先来一段日常聊天架构师玄姐问:小姚,字符串...
  • 串的模式匹配

    2020-03-13 22:53:03
    串的模式匹配是指子串的定位操作,也就是求子串(模式串)在主串中的位置; 1.暴力模式匹配(BF)算法 初始化两个数组下标,循环比较两个字符串的字符是否相等,相等则下标同时进一,比较下个元素直到匹配成功;不相等...
  • KMP模式匹配算法

    2019-08-26 22:06:38
    KMP算法:串的模式匹配指的是在主串中查找模式串的过程,主要有Brute-Force算法和KMP算法 Brute-Force算法: Brute-Force算法是最简单的暴力查找,它从主串的第一个字符开始和模式串的第一个字符进行比较,如果...
  • -定义和模式匹配算法

    千次阅读 2017-03-12 21:38:59
    5.2 串的定义 今天我们就是来研究"串"这样的数据结构。先来看定义。 串( string )是由零个或多个字符组成的有限序列,又名叫字符串 。...ai(1串中的字符数目n称为串的长度,定义中谈到"有限"是指长度n是一个有限的
  • 1、设有两个串:目标串target和模式串pattern,在目标串target中查找与模式串pattern相等的一个子串并确定该子串位置的操作成为串的模式匹配。(1)这里的相等是指:长度相等,且各对应字符相同(2)这里介绍两种...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 283
精华内容 113
关键字:

串的模式匹配算法是指