QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2938|回复: 0
打印 上一主题 下一主题

(算法)通俗易懂的字符串匹配KMP算法及求next值算法

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2021-8-10 16:12 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    (算法)通俗易懂的字符串匹配KMP算法及求next值算法
    5 ]6 b3 k" N; t7 \
    3 K" m* L: Q! S6 A% Y) V大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。. ~' S) |( M5 N2 F7 u& e1 L$ T
    5 K% Y$ E3 ?' P) Q

    , v. N- n, [2 f' v3 M4 c本文的逻辑顺序为1 I; h) c* r4 K0 c% L7 K% L
    1、最基本的朴素算法
    ! J8 [6 }% S% V) _, p. {2、优化的KMP算法
    7 k5 q; h0 l7 L4 j  [& {3、应算法需要定义的next值
    . ?/ R) a% n3 o$ Y: d4、手动写出较短串的next值的方法
    4 x" t5 C* v% v. ]- z5、最难理解的、足足有5行的代码的求next值的算法
    + |" C% N# z5 @3 X# j所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…
    # r% i2 }/ ]8 J2 a6 R- D" i! n. L- t: s2 X/ p( }

      n* C( B" |3 n, n/ R/ o! G一、问题描述
    , [1 r$ }9 ~3 {3 `0 f: V9 b给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。# z6 _  _3 a+ R# k! y

    ' i. M" o% P+ K9 Q4 ^5 @9 @1 L
    4 g/ [" H$ ~' _2 s
    二、朴素算法5 T/ H' p* o6 ?
    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:
    - W' d3 c) ^0 m0 ~, I 1111.gif " s2 L- b1 _) J$ u8 Z* X- Q4 r! A
    ( M4 C. a# Z$ v
    5 D3 C2 u7 I4 H% f! D+ g+ D. \3 |! C
    ) d& y: [1 E2 y' P# u; }
    这个算法简单,不多说,附上代码8 R9 a4 i" y( j# ~* |- A/ [. D, l

    8 X8 \6 N( U4 G% B  T- t

    # r. ]; ]; ]4 m1 n% S! b#include<stdio.h>  r% W0 h3 {/ g1 R+ y5 X( l+ Y' w
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
    , m) T; A9 F* ?, N  k. w7 y    if(sLen<pLen)return 0;
    8 K% m# A. j4 `. N4 p7 d    int i = 1,j = 1;# D" l& w# N. w5 d8 P& w& J
        while(i<=sLen && j<=pLen){0 o2 W. U* i2 M  r' ?4 U
            if(s==p[j]){i++;j++;}1 }4 d) k/ `/ i7 p! {
            else{
    8 e  m- w' g4 r# h            i = i-j+2;
    ) Q9 l3 C" K6 Q3 Y; Z            j = 1;
    . g% x" C- p/ y) B: N3 B$ L        }8 S# n* A+ g8 O9 ~
        }
    6 s! ^' ^+ l: e    if(j>pLen) return i-pLen;
    $ C; S( g( |  A& L/ v    return 0;
    & ?! g8 k5 M* i/ y5 M- v}6 P5 T$ _2 _3 G5 O7 T) t- ~/ K) p
    void main(){% z, H$ S' m- X' `/ ~
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存* f! o0 y# |% L( h; j* t# n; ^
        char p[]={' ','a','b','a','a','b','c','a','c'};1 D/ y* p3 I- f7 G$ k' H
        int sLen = sizeof(s)/sizeof(char)-1;9 f7 d8 k! @$ Y  w/ q
        int pLen = sizeof(p)/sizeof(char)-1;, M( J' b& f4 D/ N+ q
        printf("%d",Index_1(s,sLen,p,pLen));4 L" ]" L+ N: Y) S" G1 l
    }
    $ b6 b, x5 |1 |4 k" h  }1$ t0 t! \$ T4 R& s4 }/ a' x8 Y# T
    2) Q* a2 c" g2 |5 A
    3
    . A9 K) V8 O; C$ X' ]47 r7 L' b+ L- ~7 p+ U
    5
    7 x; |+ g7 {- v) N* o1 e; C% b6 u6
    4 A4 P* ?  k( v3 g7
    2 T6 p0 j/ `: X& x6 ]% ~5 }; f3 T5 C89 ~) G: ^8 z; `8 I. a% R
    9
    # M7 o: @% v' b7 x( s& L# n10
    ( b6 h1 V7 Z  r; L$ m& r. R. {11
    0 S# U: _, d2 F0 {6 ^12
    7 i; D" y- O6 i' f13- |0 I" m  C" b* U
    14( W" n: x+ q( G4 l" x4 x
    15
      q- U/ ]2 ?7 R! l# _16  Y. X& d, u$ t0 M$ Z4 p2 y* n
    17
    6 r* ^, \% p6 _' g3 b18
    ( E/ G- K  j; P/ e2 q: m+ Q. l19+ j8 w) H6 n6 q, d
    20, k6 [8 A% \4 e% t: O* e  C
    21
    # }5 M" Y# x3 @5 Y4 ~. ~* ~' D- m* n三、改进的算法——KMP算法
    " D8 X( e" h+ f  ~: U0 R3 |朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    4 g, X: J: S* H2 i一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。  q+ |; L  Z3 s) x" k8 H, {
    朴素算法中,P的第j位失配,默认的把P串后移一位。1 e; A( x2 S( K1 k3 D8 j
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:: k5 p, c% g& }8 q8 c0 F

    1 d7 ]9 c$ d" e" x$ e  j
    222.gif
    " I6 t5 }+ B, ]0 P& x7 d2 C# \4 E) b" j- ]  k) y; o! i
    3 }* e7 b3 ]5 \
    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。! `2 @: q/ R  B* i+ C
    , T) H- u2 J. y9 p' g6 k
    / n* C1 \. f" Q+ ]( D9 k# Q
    相比朴素算法:
    3 p1 o. s. r/ J: r9 _& e朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    " V! w6 j! D4 f2 l  ^KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高7 h3 O- ~: o$ `: w9 E; N

    - _9 Z, w4 |/ Y  v0 h! Z: Q; {9 ~1 ~

    4 u! L% w; O% d. r1 U# @9 v而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)1 T( _; y) u" O5 S9 d! F. J" F
    ; @) Y' L! O! u! a" e) t
    " v  O* V8 ^. R
    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)
    - g# d+ T9 J# ?2 ?. V# P" [* K, k
    5 U; B4 C$ v9 ~" C* A  i

    / V5 W7 R2 ^$ D5 g# t' P; B比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      _6 V. v. f4 \7 B
    333.png
    + x& {& n$ h# j* N* e) j' g$ G, \4 K& H( _
    # T/ b) \0 r+ F; q( G4 `
    假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
    - h. E( ~- O7 a
    ' v& Q' ]  b+ T
    4444.png 7 w  l7 ]% F, ?" b- @
    + H  M: @  f0 Y

    ) V! H  y$ \; ]' f! N那么可以推出,P1…Pk-1与Si…Si+j-2
    4 l9 C' I2 E+ ]5 [8 }$ D" N& z4 y5 c5 m+ b) h' ~
    555.png ) U9 m% M( o% d: O6 h% E

    & s3 }- e' L+ ~6 d4 J

    ' x% O5 d1 o# I) g显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
    4 d. S) t7 F. ~4 M3 M$ v+ r2 \, W: l4 B: z+ U
    666.png
    * K/ P1 {7 N8 ]  \
    ) X% s' g+ ?1 N2 i1 P9 e

    . G3 X6 u, @% C4 S. k5 F为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。6 `' \2 l# s8 X0 }& z

    1 B8 B( e) j& H; d* _$ V  r. G

    3 p3 _+ J' P; b/ Q4 G( T$ q, s3 ~最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。2 h8 B3 C' L$ J, G; G# d

      G) f2 T* S6 Z; G
    % D$ i) \; @" m5 X- O: p, X$ a! S
    四、手动写出一个串的next值; C. O, G$ S: Z0 ]+ H+ Z* T
    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    3 {6 i" Q- ^8 s! i! A" x" i; a
    - Q( c3 j$ E. I" \+ p
    7777.gif 5 m. m+ j" {* i$ L: s. ]
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。0 }, z- L, l$ u1 x! A

    * \  Q8 u' x. E( v3 J9 @% l3 C
    . ]1 |3 G! V5 D! X$ T
    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:4 {( }* L1 R% B0 k( T! n  o+ t# v
    7 L, @2 y& K( T* n4 I% G

    ' K& _) P( ?- w- [
    8888.png 2 }! U7 T9 U2 v' C  ~/ H: Z

    , t( e- w# Z0 x1 j& G: D五、求next的算法
    5 z- r) p4 G, G9 A终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。
      s! s5 e9 P% H7 [8 {
    ) h5 [" d  v& R

    # t; x7 Z6 I- i# C- D! a" p/ @int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度, h9 w% S* l- z
        next[1] = 0;% C1 k6 w, J4 o+ n8 Z( G
        int i = 1,j = 0;
    1 J$ y: |$ r; D1 _9 N2 ~    while(i<=cLen){
    9 q( |/ O( l2 O# B6 C/ Z        if(j==0||ch==ch[j]) next[++i] = ++j;
    ) {7 w2 P9 u0 Y4 L0 m: w" l) _        else j = next[j];$ h& I( F/ @4 w9 f7 D- N  }
        }
    1 ?' }6 g9 D" y8 F}" ^) d6 u2 x# k" b
    4 h/ r% e' L- |% n/ K
    还是先由一般再推优化:- ~7 n" _, R$ l* e5 F
    直接求next[j+1](至于为什么是j+1,是为了和下面的对应)8 V+ }" r( ^0 V
    根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
    8 y- C6 \, N7 |  H不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
    6 n# N) A  `3 O0 Xif(P1…Pj-1 == P2…Pj) => next[j+1]=j' X  Q+ v; g- z7 z/ Y; I
    else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1) p+ \" V0 u+ m7 S( S3 h
    else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
    - [1 V5 Y# S4 y2 h& u2 [/ b' t) q% _% k

    ) u! x! K! Y* J" ?7 N- l! h
    6 V4 {' ~( n5 j, q7 N2 Celse if(P1P2 == Pj-1Pj) => next[j+1]=3
    0 f, o; r6 ]  belse if(P1 == Pj-1) => next[j+1]=29 Y% l/ r, \! h6 J2 i. w
    else if(P1 != Pj-1) => next[j+1]=12 U9 v3 q- h" M1 T. f# `. o" y/ W# b
    每次前去尾1个,后掐头1个,直至得到next[j+1]
    / X, K1 Y$ O% W! p( m" J6 M: x0 z3 n  G

    7 t, u! ?5 ^8 Q/ o再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。
    * ?8 Y- x% U9 v! G但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,7 j: l( p6 }: a7 S! Y& d3 ?
    ①next[j+1]的可能的最大值是多少(即从哪开始验证)
    , E4 d8 W/ A) J4 t5 W# p" k②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
    8 Z" }* [: v7 `看一下的分析:, C4 i: x8 Y' X5 `

      N& M1 d# w- U- W7 h' J5 G% l
    + z1 x8 i" O; I5 u1 s, l& I
    1、next[j+1]的最大值为next[j]+1。
    4 T; G; k) B$ l1 M! Y因为:
    * T8 s; Y/ y0 }/ B0 q$ T/ e1 ?7 t假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    0 \, R) W1 S7 C5 ?* d! d# Q7 X& w如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    * d6 M& e6 X# }6 B; b2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]7 H9 r) {+ U3 n$ Y1 E
    这里不好解释,直接看下面的流程分析及图解
    ; ]+ A; d; [" n7 U6 b5 r/ ~: a- a$ G' u* R& X  R1 c$ b" T) o& d

    5 y! Q' ^+ r# y. y) |+ o! i开——始——划——重——点!
    8 g' M9 W7 k2 r' \2 s( p从头走一遍流程
    : s! O# V* Q. f6 b①求next[j+1],设值为m
    4 A6 s* J. \, @' \' \②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1/ o, m8 q3 P" \2 R$ E7 [# F" ^( F
    ③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则+ s1 a* w7 o9 t& s  |( |
    ④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
      g/ t8 V# @6 c8 n⑤第二第三步联合得到:
    0 k' u, f) J$ Q/ m8 S; nP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ' T$ u* h1 C* j# E7 {⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推
    & y$ q9 `: [2 o) s3 `. ^0 f+ L7 x9 @5 z; v& R
    ! D" J6 s- n. L7 r
    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:- W6 R) M4 ~7 k
    1、要求next[k+1] 其中k+1=170 n  i; ^, U( |; X6 g
    999.png . _  f/ a2 j# r' z2 }
    # O. c- m! [0 X
    2、已知next[16]=8,则元素有以下关系:
    # d+ H/ v8 p% r
    10.png % G  l: [( L) f4 B& V$ m: T

    7 v- ^6 i1 h$ L( M$ H0 Z3、如果P8=P16,则明显next[17]=8+1=9
    ) @% C# |, H. _. D3 N4、如果不相等,又若next[8]=4,则有以下关系5 H% ?% e7 V0 ^/ y# I7 m# l( h
    : L5 \0 t( S- |0 `6 M. ?. O0 L
    11.png
    7 h1 p3 G( M% ~$ [又加上2的条件知
    ; \& a' W" o0 x1 g; `' H, I: q4 D, h8 J& k* |# t, Q2 n
    12.png 1 f; |7 d& M! ^1 K8 k
    主要是为了证明:! C0 ]8 X; A! D  }5 R( E- Q- @
    13.png 3 N# j  q, e" I# T

    ! b4 e( n' t; J% s* B, M6 B* w" K5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    0 z4 ~5 ?+ E" t6 b* V& L1 P* e6、若next[4]=2,则有以下关系# S; C5 w% Q' z) X
    14.png & t( Z) Z4 V, R6 f5 M

    3 m' g. M+ \" q( e: M6 {7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!" }. l& V4 \4 I5 H+ ]
    ————————————————
      Z% d) ~1 I* V* M1 P, ^版权声明:本文为CSDN博主「Sirm23333」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。7 {1 t+ \! g% b9 I# j7 Q
    原文链接:https://blog.csdn.net/qq_37969433/article/details/82947411
    , X8 ~- R+ q$ m* n$ V$ Z6 v% S& R5 P) R3 e

    & |, I  r4 p( _! r

    6 P- ^( A! I! i, y
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-7-30 18:05 , Processed in 0.379209 second(s), 53 queries .

    回顶部