精华内容
下载资源
问答
  • 扩展KMP算法讲解

    2019-04-08 20:02:31
    扩展KMP算法用处: 问题定义:给定两个字符串S和T(长度分别为n和m),下标从0开始,定义extend[i]等于S[i]...S[n-1]与T的最长相同前缀的长度,求出所有的extend[i]。举个例子,看下表: i 0 1 2 3 ...

    扩展KMP算法用处:

    问题定义:给定两个字符串S和T(长度分别为n和m),下标从0开始,定义extend[i]等于S[i]...S[n-1]与T的最长相同前缀的长度,求出所有的extend[i]。举个例子,看下表:

    i 0 1 2 3 4 5 6 7
    S a a a a a b b b
    T a a a a a c    
    extend[i] 5 4 3 2 1 0 0 0

    为什么说这是KMP算法的扩展呢?显然,如果在S的某个位置i有extend[i]等于m,则可知在S中找到了匹配串T,并且匹配的首位置是i。而且,扩展KMP算法可以找到S中所有T的匹配。接下来具体介绍下这个算法。

    一:算法流程

    (1)

    如上图,假设当前遍历到S串位置i,即extend[0]...extend[i - 1]这i个位置的值已经计算得到。设置两个变量,a和p。p代表以a为起始位置的字符匹配成功的最右边界,也就是"p = 最后一个匹配成功位置 + 1"。相较于字符串T得出,S[a...p)等于T[0...p-a)

    再定义一个辅助数组int next[],其中next[i]含义为:T[i]...T[m - 1]与T的最长相同前缀长度,m为串T的长度。举个例子:

    i 0 1 2 3 4 5
    T a a a a a c
    next[i] 6 4 3 2 1 0

    (2)

      

    S[i]对应T[i - a],如果i + next[i - a] < p,如上图,三个椭圆长度相同,根据next数组的定义,此时extend[i] = next[i - a]

    (3)

     

    如果i + next[i - a] == p呢?如上图,三个椭圆都是完全相同的,S[p] != T[p - a]T[p - i] != T[p - a],但S[p]有可能等于T[p - i],所以我们可以直接从S[p]T[p - i]开始往后匹配,加快了速度。

    (4)

     

    如果i + next[i - a] > p呢?那说明S[i...p)T[i-a...p-a)相同,注意到S[p] != T[p - a]T[p - i] == T[p - a],也就是说S[p] != T[p - i],所以就没有继续往下判断的必要了,我们可以直接将extend[i]赋值为p - i

    (5)最后,就是求解next数组。我们再来看下next[i]extend[i]的定义:

    • next[i]: T[i]...T[m - 1]与T的最长相同前缀长度;
    • extend[i]: S[i]...S[n - 1]与T的最长相同前缀长度。

    恍然大悟,求解next[i]的过程不就是T自己和自己的一个匹配过程嘛,下面直接看代码。

    二:代码

    *数据测试如下:

    aaaaabbb
    aaaaac
    next:   6 4 3 2 1 0
    extend: 5 4 3 2 1 0 0 0
    
    abc
    def
    next:   3 0 0
    extend: 0 0 0
    #include <iostream>
    #include <string>
    using namespace std;
    /* 求解 T 中 next[],注释参考 GetExtend() */
    void GetNext(string & T, int & m, int next[])
    {
        int a = 0, p = 0;
        next[0] = m;
    
        for (int i = 1; i < m; i++)
        {
            if (i >= p || i + next[i - a] >= p)
            {
                if (i >= p)
                    p = i;
    
                while (p < m && T[p] == T[p - i])
                    p++;
    
                next[i] = p - i;
                a = i;
            }
            else
                next[i] = next[i - a];
        }
    }
    
    /* 求解 extend[] */
    void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
    {
        int a = 0, p = 0;
        GetNext(T, m, next);
    
        for (int i = 0; i < n; i++)
        {
            if (i >= p || i + next[i - a] >= p) // i >= p 的作用:举个典型例子,S 和 T 无一字符相同
            {
                if (i >= p)
                    p = i;
    
                while (p < n && p - i < m && S[p] == T[p - i])
                    p++;
    
                extend[i] = p - i;
                a = i;
            }
            else
                extend[i] = next[i - a];
        }
    }
    
    int main()
    {
        int next[100];
        int extend[100];
        string S, T;
        int n, m;
        
        while (cin >> S >> T)
        {
            n = S.size();
            m = T.size();
            GetExtend(S, n, T, m, extend, next);
    
            // 打印 next
            cout << "next:   ";
            for (int i = 0; i < m; i++)
                cout << next[i] << " ";
     
            // 打印 extend
            cout << "\nextend: ";
            for (int i = 0; i < n; i++)
                cout << extend[i] << " ";
    
            cout << endl << endl;
        }
        return 0;
    }

     

    展开全文
  • 扩展kmp算法讲解

    2016-02-22 15:53:45
    扩展kmp得到的是什么 字符串A,B。B是模式串(子串)。求解A[i ……lenA -1]与B的最长公共前缀,记录在数组ex[i]中 二.算法实现 分为两步,第一步是对B模式串进行处理也是求B[i,Blen - 1]与B的最长公共前缀,用...

    参考文章http://www.cnblogs.com/10jschen/archive/2012/09/03/2668149.html

    一.扩展kmp得到的是什么

    字符串A,B。B是模式串(子串)。求解A[i ……lenA -1]与B的最长公共前缀,记录在数组ex[i]中

    二.算法实现

    分为两步,第一步是对B模式串进行处理也是求B[i,Blen - 1]与B的最长公共前缀,用next数组存储,第二部是将A与B进行匹配,其实他们的方法是一样的

    我们先对第二步进行分析

    首先假设B的nexta[]的值已经全部求出,且i之前全部的ex值也已经求出,再设p为匹配过程中的最大位置,设k为达到最大位置时的起始位置,由此可知p = k + ex[k] - 1

    由ex的定义可知:A[k……k + ex[k] -1]   与B[0……ex[k] - 1]相等 显然i > k  所以 A[i……k + ex[k] - 1]  

    与 B[i - k……ex[k]-1] 匹配,设L = nexta[i - k],根据nexta的定义有B[0……L-1]  = B[i-k……i - k + L - 1]

    只需判断ex[k] - 1(=p - k ) 与 i - k + L - 1那个大

    1.i - k + L - 1 < p - k    及 p > i + L - 1,p >= i + L

    A[i……p]  与 B[i - k……p-k] 匹配得到A[i……L + i - 1]B[i - k……i - k + L - 1] ,又有B[0……L-1]  = B[i-k……i - k + L - 1]。故A[i……L + i - 1] = B[0……L-1]  可知ex[i] >= L,如果ex[i] > L则A[i……L + i ] = B[0……L] .因为p = k + ex[k] - 1 >= i + L,所以A[i……L + i] = B[i - k……i - k + L],推出B[0……L] = k + ex[k] - 1与next数组定义不符合。所以ex[i] = L

    2.i - k + L - 1 >= p - k    及 p <= i + L - 1,p < i + L

    A[i……p]  = B[i - k……p-k]

    B[0……L-1]  = B[i-k……i - k + L - 1] 所以B[0……p -i]  = B[i-k……p - k]

    所以A[i……p]  = B[0……p -i],p是匹配到的最远的地方,需要继续从A[p + 1] 和 B[p - i + 1]开始继续匹配

    设j = p - i + 1,则 p  + 1 = i + j。p增加了,所以要更新p和k的值

    ps:注意j如果是小于零的就让j = 0,从B的最前端开始匹配

    第一步显然和第二步的方法是一样的,注意第一步中都是nexta数组

    对于B来说nexta[0]  肯定等于n,然后求出nexta[1]的最远距离,另k = 1,不用对p赋值

    对于AB匹配来说,要遍历求出extend[0],遍历应该到两个字符串中长度较短的一个就停止。并另k = 0。

    代码如下

    //需定义extend 和 nexta
    void EKMP(char s[],char t[])//s主串,t模式串
    {
        memset(nexta,0,sizeof(nexta));
        memset(extend,0,sizeof(extend));
        int slen = strlen(s),tlen = strlen(t);
        int len = min(slen,tlen);
        nexta[0] = tlen;
        int k;
        for(k = 0;k + 1 < tlen && t[k] == t[k + 1];k ++ )
        {
        }
        nexta[1] = k;
        k = 1;
        int p,L,j;
        for(int i = 2; i < tlen; i ++)
        {
            p = k + nexta[k] - 1, L = nexta[i - k];
            if(i + L <= p)
            {
                nexta[i] = L;
            }
            else
            {
                j = p - i + 1;
                if(j < 0)
                    j = 0;
                while(i + j < tlen && t[i + j] == t[j])
                {
                    j++;
                }
                nexta[i] = j;
                k = i;
            }
        }
        for(k = 0;k < len && s[k] == t[k];k ++ )
        {
        }
        extend[0] = k;
        k = 0;
        for(int i = 1; i < slen; i ++)
        {
            p = k + extend[k] - 1, L = nexta[i - k];//注意p是加extend
            if(i + L <= p)
            {
                extend[i] = L;
            }
            else
            {
                int j = p - i + 1;
                if(j < 0)
                    j = 0;
                while(i + j < slen &&j < tlen && s[i + j] == t[j])
                {
                    j++;
                }
                extend[i] = j;
                k = i;
            }
        }
    }



    展开全文
  • KMP算法讲解

    2019-01-07 17:23:00
    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

    以上是百度百科对KMP算法的介绍,如何把实现把朴素算法变成O(m+n)的时间复杂度呢,从上面介绍可以看出来,KMP算法利用了一个next数组,所以需要预处理,下面我们就来讲解KMP算法。

    因为懒得画图还怕画不好,所以我录制成了视频的格式。

    Bilibili视频:https://www.bilibili.com/video/av40137935

    这是一道KMP裸题,请自行尝试AC:传送门

    看完上面,你大致就应该清楚如何利用KMP进行线性匹配了,但是KMP算法的精髓其实不是进行简单的串匹配,精髓应该在于next数组的应用,以及扩展的next_val数组的运用,可以快速的寻找循环节,前缀匹配等等一些复杂的字符串问题。

    下面将以一道例题说明next数组的强大

    HDU 1358(Period)

    Problem Description
    For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A K , that is A concatenated K times, for some string A. Of course, we also want to know the period K.
    Input
    The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) - the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.
    Output
    For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
    SampleInput
    3
    aaa
    12
    aabaabaabaab
    0
     
    SampleOutput
    Test case #1
    2 2
    3 3
    
    Test case #2
    2 2
    6 2
    9 3
    12 4

    题意:给一个长为n的字符串,问字符串的前缀是不是周期串,如果是周期串,输出前缀的最后一个字母的位置和最短周期

    应该如何思考呢,已经说明了这是一道KMP的题,用KMP进行串匹配吗?显然不是,那么肯定就是利用next数组的性质了,对于前i个字符,如果next[i]不等于零,那么说明在此字符串的前缀中,有一部分[0,next[i]]和本字符串[i-next[i],i]的这一部分是相同的。如果这i个字符组成一个周期串,那么错开的一部分[next[i],i]恰好是一个循环节。(换句话说,如果满足next[i]不等于零 && [next[i],i]是循环节这两点,就可以说明前i个字符组成一个周期串),那么我们只需要跑一遍next数组即可,代码:

     1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 int n;
     5 string str;
     6 int nxt[1000005];
     7 
     8 void getnext(){
     9     int i = 0, j = -1, len = str.size();
    10     nxt[0] = -1;
    11     while(i < len){
    12         if(j == -1 || str[i] == str[j])
    13             nxt[++i] = ++j;
    14         else
    15             j = nxt[j];
    16     }
    17 }
    18 
    19 int main(){
    20     ios_base::sync_with_stdio(false),cout.tie(0),cin.tie(0);
    21     int tot = 1;
    22     while(cin>>n && n){
    23         cin>>str;
    24         getnext();
    25         cout << "Test case #" << tot++ << endl;
    26         for(int i = 2; i <= n; i++){
    27             if(nxt[i] != 0 && i % (i - nxt[i]) == 0)
    28                 cout << i << " " << i/(i - nxt[i]) << endl;
    29         }
    30         cout << endl;
    31     }
    32 
    33     return 0;
    34 }

     

    关于KMP算法就讲到这里了,这是一个很简单的串匹配算法,但能否掌握其思想以及运用其next数组,就得靠自己不断的磨练了。

    转载于:https://www.cnblogs.com/xenny/p/10024474.html

    展开全文
  • kmp算法讲解

    2017-05-02 19:02:00
    看到kmp是不是立即想到(*@ο@*) 哇~,那个东西啊,就是拿来放电影的那个啊! 哦,但是这里我们说的并不是那个东西,身为一名C++选手,我们肯定说的是一种算法了!!! 换句换说:给你两个字串,你要告诉我,B串...

    转自——http://blog.csdn.net/v_july_v/article/details/7041827

    看到kmp是不是立即想到(*@ο@*) 哇~,那个东西啊,就是拿来放电影的那个啊!

    哦,但是这里我们说的并不是那个东西,身为一名C++选手,我们肯定说的是一种算法了!!!

    换句换说:给你两个字串,你要告诉我,B串是否是A串的子串(A串是否包含B串)。比如,字符串A="I'm matrix67",字符串B="matrix",我们就说B是A的子串。你可以委婉地问你的MM:“假如你要向你喜欢的人表白的话,我的名字是你的告白语中的子串吗?”

    说笑归说笑,那你知道该怎样求这个子串吗??

    暴力匹配算法(肯定超时!!!)

        假设现在我们面临这样一个问题:有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找呢?

        如果用暴力匹配的思路,并假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置,则有:

    • 如果当前字符匹配成功(即S[i] == P[j]),则i++,j++,继续匹配下一个字符;
    • 如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0。
       来我们上暴力程序
    int baoli
    {
        int i=0,j=0;
        int ll=strlen(a); 
        int ld=strlen(b);
        while (i < ll && j < ld) 
         {
             if(a[i]==b[j])//可以匹配 
             {
                 i++;
                 j++;
             }
             else//不能匹配 
             {
                 i=i-j+1;
                 j=0;
             }
         }
         if(j==ld)
         {
             return i-j;
         }
         else return -1;
    } 

        举个例子,如果给定文本串S“BBC ABCDAB ABCDABCDABDE”,和模式串P“ABCDABD”,现在要拿模式串P去跟文本串S匹配,整个过程如下所示:

        1. S[0]为B,P[0]为A,不匹配,执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[1]跟P[0]匹配,相当于模式串要往右移动一位(i=1,j=0)

        2. S[1]跟P[0]还是不匹配,继续执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[2]跟P[0]匹配(i=2,j=0),从而模式串不断的向右移动一位(不断的执行“令i = i - (j - 1),j = 0”,i从2变到4,j一直为0)

        3. 直到S[4]跟P[0]匹配成功(i=4,j=0),此时按照上面的暴力匹配算法的思路,转而执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,可得S[i]为S[5],P[j]为P[1],即接下来S[5]跟P[1]匹配(i=5,j=1)

         

        4. S[5]跟P[1]匹配成功,继续执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,得到S[6]跟P[2]匹配(i=6,j=2),如此进行下去

        

        5. 直到S[10]为空格字符,P[6]为字符D(i=10,j=6),因为不匹配,重新执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,相当于S[5]跟P[0]匹配(i=5,j=0)

         

        6. 至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了S[9]、P[5],但因为S[10]跟P[6]不匹配,所以文本串回溯到S[5],模式串回溯到P[0],从而让S[5]跟P[0]匹配。

        而S[5]肯定跟P[0]失配。为什么呢?因为在之前第4步匹配中,我们已经得知S[5] = P[1] = B,而P[0] = A,即P[1] != P[0],故S[5]必定不等于P[0],所以回溯过去必然会导致失配。那有没有一种算法,让i 不往回退,只需要移动j 即可呢?

        答案是肯定的。这种算法就是本文的主旨KMP算法,它利用之前已经部分匹配这个有效信息,保持i 不回溯,通过修改j 的位置,让模式串尽量地移动到有效的位置。

     

    3. KMP算法

    3.1 定义

        Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
        下面先直接给出KMP的算法流程(如果感到一点点不适,没关系,坚持下,稍后会有具体步骤及解释,越往后看越会柳暗花明☺):
    • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置
      • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
      • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。
        • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文的3.3.3节中详细阐述),即移动的实际位数为:j - next[j],且此值大于等于1。
        很快,你也会意识到next 数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。例如如果next [j] = k,代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
        此也意味着在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j 之前的某个字符,而不是跳到开头,且具体跳过了k 个字符。
        来,直接看代码!!
     
    int kmp(char*s,char*p)
    {
        int i=0,int j=0;
        int slen=strlen(s);
        int plen=strlen(p);
        while(i<slen&&j<plen)
        {
            if(j==-1||s[i]==p[j])
            {
                i++;
                j++;
            }
            else
            {
                j=next[j];
            }
        }
        if(j==plen)
          return i-j;
        else return -1;
    }
        继续拿之前的例子来说,当S[10]跟P[6]匹配失败时,KMP不是跟暴力匹配那样简单的把模式串右移一位,而是执行第②条指令:“如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]”,即j 从6变到2(后面我们将求得P[6],即字符D对应的next 值为2),所以相当于模式串向右移动的位数为j - next[j](j - next[j] = 6-2 = 4)。
        向右移动4位后,S[10]跟P[2]继续匹配。为什么要向右移动4位呢,因为移动4位后,模式串中又有个“AB”可以继续跟S[8]S[9]对应着,从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀,然后根据前缀后缀求出next 数组,最后基于next 数组进行匹配(不关心next 数组是怎么求来的,只想看匹配过程是咋样的,可直接跳到下文3.3.4节)。

    3.2 步骤

    • ①寻找前缀后缀最长公共元素长度
      • 对于P = p0 p1 ...pj-1 pj,寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj,那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子,如果给定的模式串为“abab”,那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示:

    比如对于字符串aba来说,它有长度为1的相同前缀后缀a;而对于字符串abab来说,它有长度为2的相同前缀后缀ab(相同前缀后缀的长度为k + 1,k + 1 = 2)。

    • ②求next数组
      • next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第①步骤中求得的值整体右移一位,然后初值赋为-1,如下表格所示:

    比如对于aba来说,第3个字符a之前的字符串ab中有长度为0的相同前缀后缀,所以第3个字符a对应的next值为0;而对于abab来说,第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a,所以第4个字符b对应的next值为1(相同前缀后缀的长度为k,k = 1)。

    • ③根据next数组进行匹配
      • 匹配失配,j = next [j],模式串向右移动的位数为:j - next[j]。换言之,当模式串的后缀pj-k pj-k+1, ..., pj-1 跟文本串si-k si-k+1, ..., si-1匹配成功,但pj 跟si匹配失败时,因为next[j] = k,相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀,即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1,故令j = next[j],从而让模式串右移j - next[j] 位,使得模式串的前缀p0 p1, ..., pk-1对应着文本串 si-k si-k+1, ..., si-1,而后让pk 跟si 继续匹配。如下图所示:
     
        综上,KMP的next 数组相当于告诉我们:当模式串中的某个字符跟文本串中的某个字符匹配失配时,模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时,下一步用next [j] 处的字符继续跟文本串i 处的字符匹配,相当于模式串向右移动 j - next[j] 位。
        接下来,分别具体解释上述3个步骤。
     

    3.3 解释

    3.3.1 寻找最长前缀后缀

        如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:
        也就是说,原模式串子串对应的各个前缀后缀的公共元素的最大长度表为(下简称《最大长度表》):
     

    3.3.2 基于《最大长度表》匹配

        因为模式串中首尾可能会有重复的字符,故可得出下述结论:
    失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值

        下面,咱们就结合之前的《最大长度表》和上述结论,进行字符串的匹配。如果给定文本串“BBC ABCDAB ABCDABCDABDE”,和模式串“ABCDABD”,现在要拿模式串去跟文本串匹配,如下图所示:

            

    • 1. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配,所以不必考虑结论,直接将模式串不断的右移一位即可,直到模式串中的字符A跟文本串的第5个字符A匹配成功:

    • 2. 继续往后匹配,当模式串最后一个字符D跟文本串匹配时失配,显而易见,模式串需要向右移动。但向右移动多少位呢?因为此时已经匹配的字符数为6个(ABCDAB),然后根据《最大长度表》可得失配字符D的上一位字符B对应的长度值为2,所以根据之前的结论,可知需要向右移动6 - 2 = 4 位。
    • 3. 模式串向右移动4位后,发现C处再度失配,因为此时已经匹配了2个字符(AB),且上一位字符B对应的最大长度值为0,所以向右移动:2 - 0 =2 位。
               
    • 4. A与空格失配,向右移动1 位。
    • 5. 继续比较,发现D与C 失配,故向右移动的位数为:已匹配的字符数6减去上一位字符B对应的最大长度2,即向右移动6 - 2 = 4 位。
               
    • 6. 经历第5步后,发现匹配成功,过程结束。

              

        通过上述匹配过程可以看出,问题的关键就是寻找模式串中最大长度的相同前缀和后缀,找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后,便可基于此匹配。而这个最大长度便正是next 数组要表达的含义。

    3.3.3 根据《最大长度表》求next 数组

        由上文,我们已经知道,字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为:

     

     

        而且,根据这个表可以得出下述结论

     

    • 失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
        上文利用这个表和结论进行匹配时,我们发现,当匹配到一个字符失配时,其实没必要考虑当前失配的字符,更何况我们每次失配时,都是看的失配字符的上一位字符对应的最大长度值。如此,便引出了next 数组。
        给定字符串“ABCDABD”,可求得它的next 数组如下:

     

     

     

        把next 数组跟之前求得的最大长度表对比后,不难发现,next 数组相当于“最大长度值” 整体向右移动一位,然后初始值赋为-1。意识到了这一点,你会惊呼原来next 数组的求解竟然如此简单:就是找最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1(当然,你也可以直接计算某个字符对应的next值,就是看这个字符之前的字符串中有多大长度的相同前缀后缀)。

        换言之,对于给定的模式串:ABCDABD,它的最大长度表及next 数组分别如下:


        根据最大长度表求出了next 数组后,从而有

     

    失配时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值

     

        而后,你会发现,无论是基于《最大长度表》的匹配,还是基于next 数组的匹配,两者得出来的向右移动的位数是一样的。为什么呢?因为:

    • 根据《最大长度表》,失配时,模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值
    • 而根据《next 数组》,失配时,模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值
      • 其中,从0开始计数时,失配字符的位置 = 已经匹配的字符数(失配字符不计数),而失配字符对应的next 值 = 失配字符的上一位字符的最大长度值,两相比较,结果必然完全一致。

        所以,你可以把《最大长度表》看做是next 数组的雏形,甚至就把它当做next 数组也是可以的,区别不过是怎么用的问题。

    3.3.4 通过代码递推计算next 数组

        接下来,咱们来写代码求下next 数组。

        基于之前的理解,可知计算next 数组的方法可以采用递推:

    • 1. 如果对于值k,已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1,相当于next[j] = k
      • 此意味着什么呢?究其本质,next[j] = k 代表p[j] 之前的模式串子串中,有长度为k 的相同前缀和后缀。有了这个next 数组,在KMP匹配中,当模式串中j 处的字符失配时,下一步用next[j]处的字符继续跟文本串匹配,相当于模式串向右移动j - next[j] 位。

    举个例子,如下图,根据模式串“ABCDABD”的next 数组可知失配位置的字符D对应的next 值为2,代表字符D前有长度为2的相同前缀和后缀(这个相同的前缀后缀即为“AB”),失配后,模式串需要向右移动j - next [j] = 6 - 2 =4位。

    向右移动4位后,模式串中的字符C继续跟文本串匹配。

    • 2. 下面的问题是:已知next [0, ..., j],如何求出next [j + 1]呢?

        对于P的前j+1个序列字符:

    • 若p[k] == p[j],则next[j + 1 ] = next [j] + 1 = k + 1;
    • 若p[k ] ≠ p[j],如果此时p[ next[k] ] == p[j ],则next[ j + 1 ] =  next[k] + 1,否则继续递归前缀索引k = next[k],而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等,那么是否可能存在另一个值t+1 < k+1,使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢?如果存在,那么这个t+1 便是next[ j+1]的值,此相当于利用已经求得的next 数组(next [0, ..., k, ..., j])进行P串前缀跟P串后缀的匹配。
       一般的文章或教材可能就此一笔带过,但大部分的初学者可能还是不能很好的理解上述求解next 数组的原理,故接下来,我再来着重说明下。
        如下图所示,假定给定模式串ABCDABCE,且已知next [j] = k(相当于“p0 pk-1” = “pj-k pj-1” = AB,可以看出k为2),现要求next [j + 1]等于多少?因为pk = pj = C,所以next[j + 1] = next[j] + 1 = k + 1(可以看出next[j + 1] = 3)。代表字符E前的模式串中,有长度k+1 的相同前缀后缀。
        但如果pk != pj 呢?说明“p0 pk-1 pk”  ≠ “pj-k pj-1 pj”。换言之,当pk != pj后,字符E前有多大长度的相同前缀后缀呢?很明显,因为C不同于D,所以ABC 跟 ABD不相同,即字符E前的模式串没有长度为k+1的相同前缀后缀,也就不能再简单的令:next[j + 1] = next[j] + 1 。所以,咱们只能去寻找长度更短一点的相同前缀后缀。
        结合上图来讲,若能在前缀“ p0 pk-1 pk ” 中不断的递归前缀索引k = next [k],找到一个字符pk’ 也为D,代表pk’ = pj,且满足p0 pk'-1 pk' = pj-k' pj-1 pj,则最大相同的前缀后缀长度为k' + 1,从而next [j + 1] = k’ + 1 = next [k' ] + 1。否则前缀中没有D,则代表没有相同的前缀后缀,next [j + 1] = 0。
        那为何递归前缀索引k = next[k],就能找到长度更短的相同前缀后缀呢?这又归根到next数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配,如果pk 跟pj 失配,下一步就是用p[next[k]] 去跟pj 继续匹配,如果p[ next[k] ]跟pj还是不匹配,则需要寻找长度更短的相同前缀后缀,即下一步用p[ next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配,所以不断的递归k = next[k],直到要么找到长度更短的相同前缀后缀,要么没有长度更短的相同前缀后缀。如下图所示:
        
        所以,因最终在前缀ABC中没有找到D,故E的next 值为0:
     
    模式串的后缀:ABDE
    模式串的前缀:ABC
    前缀右移两位:     ABC
        读到此,有的读者可能又有疑问了,那能否举一个能在前缀中找到字符D的例子呢?OK,咱们便来看一个能在前缀中找到字符D的例子,如下图所示:
        给定模式串DABCDABDE,我们很顺利的求得字符D之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为0 0 0 0 1 2 3,但当遍历到字符D,要求包括D在内的“DABCDABD”最长相同前缀后缀时,我们发现pj处的字符D跟pk处的字符C不一样,换言之,前缀DABC的最后一个字符C 跟后缀DABD的最后一个字符D不相同,所以不存在长度为4的相同前缀后缀。
        怎么办呢?既然没有长度为4的相同前缀后缀,咱们可以寻找长度短点的相同前缀后缀,最终,因在p0处发现也有个字符D,p0 = pj,所以p[j]对应的长度值为1,相当于E对应的next 值为1(即字符E之前的字符串“DABCDABD”中有长度为1的相同前缀和后缀)。
        综上,可以通过递推求得next 数组,代码如下所示:
    [cpp] view plain copy
     
     print?在CODE上查看代码片派生到我的代码片
    1. void GetNext(char* p,int next[])  
    2. {  
    3.     int pLen = strlen(p);  
    4.     next[0] = -1;  
    5.     int k = -1;  
    6.     int j = 0;  
    7.     while (j < pLen - 1)  
    8.     {  
    9.         //p[k]表示前缀,p[j]表示后缀  
    10.         if (k == -1 || p[j] == p[k])   
    11.         {  
    12.             ++k;  
    13.             ++j;  
    14.             next[j] = k;  
    15.         }  
    16.         else   
    17.         {  
    18.             k = next[k];  
    19.         }  
    20.     }  
    21. }  

        用代码重新计算下“ABCDABD”的next 数组,以验证之前通过“最长相同前缀后缀长度值右移一位,然后初值赋为-1”得到的next 数组是否正确,计算结果如下表格所示:

        从上述表格可以看出,无论是之前通过“最长相同前缀后缀长度值右移一位,然后初值赋为-1”得到的next 数组,还是之后通过代码递推计算求得的next 数组,结果是完全一致的。

    3.3.5 基于《next 数组》匹配

        下面,我们来基于next 数组进行匹配。

     

        还是给定文本串“BBC ABCDAB ABCDABCDABDE”,和模式串“ABCDABD”,现在要拿模式串去跟文本串匹配,如下图所示:

        在正式匹配之前,让我们来再次回顾下上文2.1节所述的KMP算法的匹配流程:

    • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置
      • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
      • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。
        • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值,即移动的实际位数为:j - next[j],且此值大于等于1。
    • 1. 最开始匹配时
      • P[0]跟S[0]匹配失败
        • 所以执行“如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]”,所以j = -1,故转而执行“如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++”,得到i = 1,j = 0,即P[0]继续跟S[1]匹配。
      • P[0]跟S[1]又失配,j再次等于-1,i、j继续自增,从而P[0]跟S[2]匹配。
      • P[0]跟S[2]失配后,P[0]又跟S[3]匹配。
      • P[0]跟S[3]再失配,直到P[0]跟S[4]匹配成功,开始执行此条指令的后半段:“如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++”。
    • 2. P[1]跟S[5]匹配成功,P[2]跟S[6]也匹配成功, ...,直到当匹配到P[6]处的字符D时失配(即S[10] != P[6]),由于P[6]处的D对应的next 值为2,所以下一步用P[2]处的字符C继续跟S[10]匹配,相当于向右移动:j - next[j] = 6 - 2 =4 位。

    • 3. 向右移动4位后,P[2]处的C再次失配,由于C对应的next值为0,所以下一步用P[0]处的字符继续跟S[10]匹配,相当于向右移动:j - next[j] = 2 - 0 = 2 位。

    • 4. 移动两位之后,A 跟空格不匹配,模式串后移1 位。

    • 5. P[6]处的D再次失配,因为P[6]对应的next值为2,故下一步用P[2]继续跟文本串匹配,相当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。
    • 6. 匹配成功,过程结束。

        匹配过程一模一样。也从侧面佐证了,next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位,且把初值赋为-1 即可。

    3.3.6 基于《最大长度表》与基于《next 数组》等价

        我们已经知道,利用next 数组进行匹配失配时,模式串向右移动 j - next [ j ] 位,等价于已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。原因是:

    1. j 从0开始计数,那么当数到失配字符时,j 的数值就是已匹配的字符数;
    2. 由于next 数组是由最大长度值表整体向右移动一位(且初值赋为-1)得到的,那么失配字符的上一位字符所对应的最大长度值,即为当前失配字符的next 值。

        但为何本文不直接利用next 数组进行匹配呢?因为next 数组不好求,而一个字符串的前缀后缀的公共元素的最大长度值很容易求。例如若给定模式串“ababa”,要你快速口算出其next 数组,乍一看,每次求对应字符的next值时,还得把该字符排除之外,然后看该字符之前的字符串中有最大长度为多大的相同前缀后缀,此过程不够直接。而如果让你求其前缀后缀公共元素的最大长度,则很容易直接得出结果:0 0 1 2 3,如下表格所示:

        然后这5个数字 全部整体右移一位,且初值赋为-1,即得到其next 数组:-1 0 0 1 2。

    3.3.7 Next 数组与有限状态自动机

        next 负责把模式串向前移动,且当第j位不匹配的时候,用第next[j]位和主串匹配,就像打了张“表”。此外,next 也可以看作有限状态自动机的状态,在已经读了多少字符的情况下,失配后,前面读的若干个字符是有用的。

    3.3.8 Next 数组的优化

       行文至此,咱们全面了解了暴力匹配的思路、KMP算法的原理、流程、流程之间的内在逻辑联系,以及next 数组的简单求解(《最大长度表》整体右移一位,然后初值赋为-1)和代码求解,最后基于《next 数组》的匹配,看似洋洋洒洒,清晰透彻,但以上忽略了一个小问题。

        比如,如果用之前的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它跟下图中的文本串去匹配的时候,发现b跟c失配,于是模式串右移j - next[j] = 3 - 1 =2位。

        右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知p[3] = b,与s[3] = c失配,而右移两位之后,让p[ next[3] ] = p[1] = b 再跟s[3]匹配时,必然失配。问题出在哪呢?

       

        问题出在不该出现p[j] = p[ next[j] ]。为什么呢?理由是:当p[j] != s[i] 时,下次匹配必然是p[ next [j]] 跟s[i]匹配,如果p[j] = p[ next[j] ],必然导致后一步匹配失败(因为p[j]已经跟s[i]失配,然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配,很显然,必然失配),所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢?如果出现了,则需要再次递归,即令next[j] = next[ next[j] ]。

        所以,咱们得修改下求next 数组的代码。

     

    [cpp] view plain copy
     
     print?在CODE上查看代码片派生到我的代码片
    1. //优化过后的next 数组求法  
    2. void GetNextval(char* p, int next[])  
    3. {  
    4.     int pLen = strlen(p);  
    5.     next[0] = -1;  
    6.     int k = -1;  
    7.     int j = 0;  
    8.     while (j < pLen - 1)  
    9.     {  
    10.         //p[k]表示前缀,p[j]表示后缀    
    11.         if (k == -1 || p[j] == p[k])  
    12.         {  
    13.             ++j;  
    14.             ++k;  
    15.             //较之前next数组求法,改动在下面4行  
    16.             if (p[j] != p[k])  
    17.                 next[j] = k;   //之前只有这一行  
    18.             else  
    19.                 //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]  
    20.                 next[j] = next[k];  
    21.         }  
    22.         else  
    23.         {  
    24.             k = next[k];  
    25.         }  
    26.     }  
    27. }  

        利用优化过后的next 数组求法,可知模式串“abab”的新next数组为:-1 0 -1 0。可能有些读者会问:原始next 数组是前缀后缀最长公共元素长度值右移一位, 然后初值赋为-1而得,那么优化后的next 数组如何快速心算出呢?实际上,只要求出了原始next 数组,便可以根据原始next 数组快速求出优化后的next 数组。还是以abab为例,如下表格所示:

        

     

    只要出现了p[next[j]] = p[j]的情况,则把next[j]的值再次递归。例如在求模式串“abab”的第2个a的next值时,如果是未优化的next值的话,第2个a对应的next值为0,相当于第2个a失配时,下一步匹配模式串会用p[0]处的a再次跟文本串匹配,必然失配。所以求第2个a的next值时,需要再次递归:next[2] = next[ next[2] ] = next[0] = -1(此后,根据优化后的新next值可知,第2个a失配时,执行“如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符”),同理,第2个b对应的next值为0。

    对于优化后的next数组可以发现一点:如果模式串的后缀跟前缀相同,那么它们的next值也是相同的,例如模式串abcabc,它的前缀后缀都是abc,其优化后的next数组为:-1 0 0 -1 0 0,前缀后缀abc的next值都为-1 0 0。

        然后引用下之前3.1节的KMP代码:

     

    [cpp] view plain copy
     
     print?在CODE上查看代码片派生到我的代码片
    1. int KmpSearch(char* s, char* p)  
    2. {  
    3.     int i = 0;  
    4.     int j = 0;  
    5.     int sLen = strlen(s);  
    6.     int pLen = strlen(p);  
    7.     while (i < sLen && j < pLen)  
    8.     {  
    9.         //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++      
    10.         if (j == -1 || s[i] == p[j])  
    11.         {  
    12.             i++;  
    13.             j++;  
    14.         }  
    15.         else  
    16.         {  
    17.             //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]      
    18.             //next[j]即为j所对应的next值        
    19.             j = next[j];  
    20.         }  
    21.     }  
    22.     if (j == pLen)  
    23.         return i - j;  
    24.     else  
    25.         return -1;  
    26. }  

     

        接下来,咱们继续拿之前的例子说明,整个匹配过程如下:

        1. S[3]与P[3]匹配失败。

        2. S[3]保持不变,P的下一个匹配位置是P[next[3]],而next[3]=0,所以P[next[3]]=P[0]与S[3]匹配。

        3.  由于上一步骤中P[0]与S[3]还是不匹配。此时i=3,j=next [0]=-1,由于满足条件j==-1,所以执行“++i, ++j”,即主串指针下移一个位置,P[0]与S[4]开始匹配。最后j==pLen,跳出循环,输出结果i - j = 4(即模式串第一次在文本串中出现的位置),匹配成功,算法结束。

       

    3.4 KMP的时间复杂度分析

        相信大部分读者读完上文之后,已经发觉其实理解KMP非常容易,无非是循序渐进把握好下面几点:
    1. 如果模式串中存在相同前缀和后缀,即pj-k pj-k+1, ..., pj-1 = p0 p1, ..., pk-1,那么在pj跟si失配后,让模式串的前缀p0 p1...pk-1对应着文本串si-k si-k+1...si-1,而后让pk跟si继续匹配。
    2. 之前本应是pj跟si匹配,结果失配了,失配后,令pk跟si匹配,相当于j 变成了k,模式串向右移动j - k位。
    3. 因为k 的值是可变的,所以我们用next[j]表示j处字符失配后,下一次匹配模式串应该跳到的位置。换言之,失配前是j,pj跟si失配时,用p[ next[j] ]继续跟si匹配,相当于j变成了next[j],所以,j = next[j],等价于把模式串向右移动j - next [j] 位。
    4. 而next[j]应该等于多少呢?next[j]的值由j 之前的模式串子串中有多大长度的相同前缀后缀所决定,如果j 之前的模式串子串中(不含j)有最大长度为k的相同前缀后缀,那么next [j] = k。
        如之前的图所示:
        接下来,咱们来分析下KMP的时间复杂度。分析之前,先来回顾下KMP匹配算法的流程:

     

    KMP的算法流程:

    • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置
      • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
      • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。”

        我们发现如果某个字符匹配成功,模式串首字符的位置保持不动,仅仅是i++、j++;如果匹配失配,i 不变(即 i 不回溯),模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功,算法结束。
        所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为O(n),算上计算next的O(m)时间,KMP的整体时间复杂度为O(m + n)。

     

    4. 扩展1:BM算法

        KMP的匹配是从模式串的开头开始匹配的,而1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法:Boyer-Moore算法,简称BM算法。该算法从模式串的尾部开始匹配,且拥有在最坏情况下O(N)的时间复杂度。在实践中,比KMP算法的实际效能高。

        BM算法定义了两个规则:

    • 坏字符规则:当文本串中的某个字符跟模式串的某个字符不匹配时,我们称文本串中的这个失配字符为坏字符,此时模式串需要向右移动,移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外,如果"坏字符"不包含在模式串之中,则最右出现位置为-1。
    • 好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。

        下面举例说明BM算法。例如,给定文本串“HERE IS A SIMPLE EXAMPLE”,和模式串“EXAMPLE”,现要查找模式串是否在文本串中,如果存在,返回模式串在文本串中的位置。

        1. 首先,"文本串"与"模式串"头部对齐,从尾部开始比较。"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符,它对应着模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中(相当于最右出现位置是-1),这意味着可以把模式串后移6-(-1)=7位,从而直接移到"S"的后一位。

        2. 依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在模式串"EXAMPLE"之中。因为“P”这个“坏字符”对应着模式串的第6位(从0开始编号),且在模式串中的最右出现位置为4,所以,将模式串后移6-4=2位,两个"P"对齐。

        3. 依次比较,得到 “MPLE”匹配,称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。

     

        4. 发现“I”与“A”不匹配:“I”是坏字符。如果是根据坏字符规则,此时模式串应该后移2-(-1)=3位。问题是,有没有更优的移法?

        5. 更优的移法是利用好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。
        所有的“好后缀”(MPLE、PLE、LE、E)之中,只有“E”在“EXAMPLE”的头部出现,所以后移6-0=6位。
        可以看出,“坏字符规则”只能移3位,“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数,只与模式串有关,与原文本串无关。

        6. 继续从尾部开始比较,“P”与“E”不匹配,因此“P”是“坏字符”,根据“坏字符规则”,后移 6 - 4 = 2位。因为是最后一位就失配,尚未获得好后缀。

     

        由上可知,BM算法不仅效率高,而且构思巧妙,容易理解。

     

    5. 扩展2:Sunday算法

        上文中,我们已经介绍了KMP算法和BM算法,这两个算法在最坏情况下均具有线性的查找时间。但实际上,KMP算法并不比最简单的c库函数strstr()快多少,而BM算法虽然通常比KMP算法快,但BM算法也还不是现有字符串查找算法中最快的算法,本文最后再介绍一种比BM算法更快的查找算法即Sunday算法。

        Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似:

     

    • 只不过Sunday算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
      • 如果该字符没有在模式串中出现则直接跳过,即移动位数 = 匹配串长度 + 1;
      • 否则,其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

        下面举个例子说明下Sunday算法。假定现在要在文本串"substring searching algorithm"中查找模式串"search"。

        1. 刚开始时,把模式串与文本串左边对齐:
    substring searching algorithm
    search
    ^
        2. 结果发现在第2个字符处发现不匹配,不匹配时关注文本串中参加匹配的最末位字符的下一位字符,即标粗的字符 i,因为模式串search中并不存在i,所以模式串直接跳过一大片,向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7,从 i 之后的那个字符(即字符n)开始下一步的匹配,如下图:

    substring searching algorithm
        search
        ^
        3. 结果第一个字符就不匹配,再看文本串中参加匹配的最末位字符的下一位字符,是'r',它出现在模式串中的倒数第3位,于是把模式串向右移动3位(r 到模式串末尾的距离 + 1 = 2 + 1 =3),使两个'r'对齐,如下:
    substring searching algorithm
          search
           ^

        4. 匹配成功。

        回顾整个过程,我们只移动了两次模式串就找到了匹配位置,缘于Sunday算法每一步的移动量都比较大,效率很高。完。

    转载于:https://www.cnblogs.com/z360/p/6797731.html

    展开全文
  • KMP与扩展KMP算法

    2019-04-15 22:52:55
    注意这里是数目,与KMPNext是下标不同。 注意是子串匹配 例如:字符串abcdaabcab的特征向量是(0,0,0,0,1,1,2,3,1,2) 对于每个字符,暴力比较耗时。可看出每个字符的特征值可以由它之前的字符推出:用next[i]...
  • 扩展KMP算法

    千次阅读 2014-09-02 01:46:09
    扩展KMP:  给出模板串A和子串B,长度分别为lenA和lenB,要求在线性时间内,对于每个A[i](0    求出A[i..lenA-1]与B的最长公共前缀长度,记为ex[i](或者说,ex[i]为满足A[i..i+z-
  • 扩展KMP算法详解

    2019-08-06 10:29:26
    算法描述: 设字符串T,长度为n,字符串S,长度为m。在线性时间内求出S关于T的每一个后缀的最长公共前缀。 关键部分: 两个数组(下标均从0开始),第...同KMP算法的思想一样,充分利用前面已经部分匹配的信息。 如何...
  • (1)目的:母串S,len(S)=n,子串T, len(T)=m, 两个字符串存储时下标都从0开始,suffix(i)表示S串中从下标i开始的后缀,扩展kmp算法可以求每个suffix(i)和T的最长公共前缀长度 (2)nxt[i]表示T串的suffix(i)和...
  • KMP&扩展KMP&Manacher算法基础与习题(第一更) KMP&...扩展KMP算法讲解 例题 A:HDU-2594 Simpsons’ Hidden Talents B:HDU-3336 Count the string C:HDU-4300 Clairewd’s message D...
  • 扩展KMP解决的是源串S的每一个后缀与模式串P的最长公共前缀的长度的问题,并求解出答案extend数组,例如,ababac与aba的extend数组是3 0 3 0 1 0,这里extend[i]表示s[i:5](i从0开始)与p[0:2]的最长公共前缀的长度...
  • 扩展KMP讲解与应用

    千次阅读 2013-11-11 12:29:29
    http://www.isnowfy.com/kmp-and-extend-kmp/ ------简单比较下KMP,扩展... http://3214668848.blog.163.com/blog/static/48764919200910152452182/ -----扩展KMP算法(Extend KMP)  http://duanple.blog.163.com
  • KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串...
  • 写的真好,看了不少于10篇的kmp博客,就这一篇讲解的最好,忍不住转载,实在是写的太好了!!! 作者:July 时间:最初写于2011年12月,2014年7月21日晚10点 全部删除重写成此文,随后的半个多月不断反复改进。后...
  • KMP&扩展KMP&Manacher算法基础与习题(第二更) ...KMP算法讲解 NEXT数组详解 模板 例题 A:HDU-1711 Number Sequence B:HDU-1686 Oulipo C:HDU-2087 剪花布条 D:HDU-3746 Cyclic Nack...
  • kmp与exkmp算法讲解

    2017-08-20 09:32:58
    KMP算法 KMP算法是一种线性时间复杂度的字符串匹配算法,它是对BF(Brute-Force,最基本的字符串匹配算法)的改进。对于给定的原始串S和模式串T,需要从字符串S中找到字符串T出现的位置的...在讲解KMP算法之前,有必要
  • KMP 模式匹配算法扩展 KMP 相关 前言 本文导览 KMP 算法简称 Knuth-Morris-Pratt Algorithm (中译:克努特——莫里斯——普拉特操作), 主要用于解决字符串中的模式匹配问题,本文将介绍以下几点 字符串的模式...
  • KMP&扩展KMP&Manacher算法基础与习题(第一更) ...Manacher算法讲解 例题 A:HDU-3613 Best Reward B:POJ-3974 Palindrome C:HDU-4513 吉哥系列故事——完美队形II D:HDU-3294 Girls' resear...
  • 扩展KMP】【模板】讲解

    千次阅读 2018-08-10 10:39:51
    扩展KMP】【模板】讲解 摘自 拓展kmp算法总结 1、扩展KMP是什么?解决何种问题?与KMP算法的异同? 拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的...
  • KMP 算法

    2021-05-23 00:15:00
    1、KMP算法 KMP 就是三位创造者的名字缩写 Knuth,Morris和Pratt KMP 是为了解决字符串匹配的问题,极大的提高的搜索的效率。通俗来讲也就是 在一个串中查找是否出现过另一个串 KMP 算法的时间复杂度是O(n+m), ...
  • 原作者:v_JULY_v 1. 引言 ...然近期因开了个算法班,班上专门讲解数据结构、面试、算法,才再次仔细回顾了这个KMP,在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后,...
  • KMP算法

    2018-05-14 17:29:00
    之后也在很多地方也都经常看到讲解KMP算法的文章,看久了好像也知道是怎么一回事,但总感觉有些地方自己还是没有完全懂明白。这两天花了点时间总结一下,有点小体会,我希望可以通过我自己的语言来把这个算法的一些...
  • 小白看 KMP算法

    2016-06-08 23:53:46
    KMP算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 953
精华内容 381
热门标签
关键字:

扩展kmp算法讲解