QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2577|回复: 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值算法  P5 r( Q# K" Y( \$ s
    * f8 G- N  f& d$ q& |3 Z
    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。+ L& @% \. e& K) v0 Z/ Y

    4 g# v+ }3 q  d$ ]5 z- H% q, {
    - I) T! y4 b9 d% P3 g" d" e
    本文的逻辑顺序为# Y9 E1 d7 W6 j: `3 G) L0 h5 p
    1、最基本的朴素算法: N) L. Z" c1 z" ~+ E8 Y; S
    2、优化的KMP算法- _1 H6 Y5 L* b+ z1 o! }# G* k/ t9 r
    3、应算法需要定义的next值
    4 ^0 o3 t& Z2 E8 @( m# |- @4、手动写出较短串的next值的方法7 v: j  ^' P* [: O1 }$ a) J3 Y
    5、最难理解的、足足有5行的代码的求next值的算法7 s' d+ L3 m6 H: c$ S
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…) g2 l0 R" z% H) K, _! A/ T$ W
    & f4 q+ w3 a& `" v2 O

    $ `- O# c* W4 h: l6 e; v' F一、问题描述6 w7 D! e% O% a; ^
    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。
    ; C3 b7 Z) H) g0 ?3 W3 ~3 |, w' P" C+ P; g3 `& I* T
    $ J8 w+ q% s  B$ O  j' R: V
    二、朴素算法/ _& g$ b2 y6 S: P
    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:8 I- x, e; r* y) T- s3 ~
    1111.gif
    ! O3 b+ t7 n; ?9 w" {8 @1 N0 _
    : d4 A# h/ h7 X( ^) p+ m0 {" E0 Z
    % ]% }9 H6 q9 S0 M
    . R  p( J- \+ @
    这个算法简单,不多说,附上代码3 z/ D9 k! n2 ]; d
    6 o; m0 K  ^1 e3 M8 {. l1 |
    ( u6 r" {  e& I( z8 T
    #include<stdio.h>
    & G8 _+ K# N1 m7 Mint Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数8 N  R, ~1 c( Z& ^3 F1 b6 C
        if(sLen<pLen)return 0;
    * K8 b$ n7 x" G- {    int i = 1,j = 1;
    # w8 P0 v$ U; D, [8 c# o    while(i<=sLen && j<=pLen){0 [' `5 X+ P2 }9 n
            if(s==p[j]){i++;j++;}! u5 [- l0 Y7 l7 g; _1 n4 b
            else{
    + l; Q3 `# c" S3 N3 o9 e            i = i-j+2;
    0 @/ ?- ^4 j& X: u% ^$ f            j = 1;
    , Q2 I3 G- q2 k7 k5 U7 s) Z: B        }
    % w% C4 h1 u8 L! d5 U    }
    9 ?0 b. ?& C9 M/ O( c) X8 @    if(j>pLen) return i-pLen;
    # I& Z; |. [( S: f' ]; D8 x0 s    return 0;( s1 [" s! ?/ |9 U" {7 U+ Y
    }/ N! G7 X% t3 Z6 G3 r" r, w
    void main(){
    $ r' G* W: a4 ^% b8 ~    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存& \) @* I' w* [1 }
        char p[]={' ','a','b','a','a','b','c','a','c'};
      }) y  i$ T/ U+ u    int sLen = sizeof(s)/sizeof(char)-1;
    " ~$ ~& x8 U) |    int pLen = sizeof(p)/sizeof(char)-1;
    1 _, O1 x6 ^$ K0 c    printf("%d",Index_1(s,sLen,p,pLen));5 h4 F* ~3 w. E2 ~8 t  W: f% `7 Y
    }
    ; O% V' U# u) ~# s/ Q+ Y$ g1
    ) ^3 M* A2 s, E- X* k% u* [2- c) O7 e3 s$ F
    3
    ( X8 u4 _8 V3 p4 d# x, M47 O0 x5 n( n) N9 E! a
    5
    * r  }  F, u, s" }; Z; ]6
    4 T: T5 Q2 S4 A5 z# |4 s1 c1 @* `73 j# B4 |% V( c$ C* B! t. g
    8
    ! ?8 h$ q6 L, P# T2 p) P97 X2 X2 V5 z* B4 U
    101 Q3 i* T+ m) [% Y
    11  L" A0 N4 F1 b" P# f  b5 k$ [
    12
    / h0 O: j0 b9 p) Z  M2 Q8 |13
    . v6 z  N( Z; P4 Z. N+ h5 }14
    ! A# @" R3 F( I1 |- N15
    + c. M, i% B$ U1 s/ S16
    $ Q0 c) ~+ V) x17  L1 z( U3 w$ J% D- E/ Z
    18
    5 u+ ?+ |. v, \3 h' N! \197 o6 G2 T8 U2 l9 ^! r3 Y
    20
    ' W8 O2 o5 u. z3 c  C) p/ ~21
    6 g0 k1 D' M3 X1 u& R" S三、改进的算法——KMP算法3 m& N. d; t, q
    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。. a0 u% s5 i* B+ l3 a; Q2 b# q8 M
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。. F2 r) o6 w& N$ y8 I% p9 @
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    * J, }0 B2 c  ?" A但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    & R& l/ \8 E, g% L1 y2 l1 E+ _/ ~" m- M1 }* d, n
    222.gif 4 q& K) f) U$ d0 p# D+ v$ D

    4 D* t5 k4 H* [

    & N: c5 }+ t$ O1 h% P& n2 d这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。. W: U2 M: [: O

    & T5 }1 x& l  U' z! Z4 q: E

    / Y- j7 p  h9 S: C: G+ K相比朴素算法:
    ) u. \0 K/ D0 R1 @6 B; M3 o朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)6 k8 ~8 y2 D$ \! \# _+ s
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高
    % y5 N: W- R, G! Z% x5 d
    % o. X- y0 P9 C* C$ `+ _

    ! B& x! @3 c) v% N% [; F  _而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)
    ; J7 ^2 |8 {" u
    8 O. d; f* i$ l
    ) y0 |; M# u; K# H8 y. F
    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)3 O3 T( c, j; d

    8 y8 H# b, e# \" T% t2 x

    ; W0 c+ d0 K/ f3 ~' j比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
    : C5 X! v' o3 k2 r6 b0 B) b
    333.png / m- y; C9 S- ?4 p5 `9 q; r
      J* {5 ]4 ]* ~6 S) h3 C; [& E

    $ g" G) Z& r9 o假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
    6 S% g" N3 K+ m" q$ C/ a3 K
    3 R- k2 E# R2 N* \
    4444.png
    ( R! E! D$ P$ Y3 P$ b4 r3 u8 [1 H: @/ g2 N9 y  o# D
    6 N* J& o7 p( ]6 V1 d' q
    那么可以推出,P1…Pk-1与Si…Si+j-26 O+ o+ g* U5 E; G) x, ]

    * ^$ y6 i* G' k. X2 [# K8 |
    555.png 9 F& c( Y3 }" _: q% o& x1 j7 s

    & W3 B" c, \, D, L, K# P4 t: R

    9 p' @, X6 y; J7 |) J: f1 v. J+ K' {显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:. X: S. Z4 p3 N6 h

    & k* U5 H# m( k* W$ c& Y, c3 f
    666.png
    9 F4 R/ [; s: X' _  O6 ?$ P; L( [) I/ F8 D! ^3 |, l

    ' M4 T5 Q1 v, S  m& x( w3 o0 W为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。! j0 Z" {& I& u

    . k: z, e1 k- r3 x0 |

    : L* M: E% t5 C5 s/ S2 j& @% f最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。5 I3 K, E( p: D+ g7 I
    7 `2 h& p# ?# p: D

    4 P9 E( m- a- Q! v4 T! N( l四、手动写出一个串的next值, T1 l( ~; u- `3 v( E
    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    # I* Z7 z1 A% A  b; _* E
    3 o. t( B& Z9 E3 i: x- s
    7777.gif % P) h& u% X$ \1 d* V7 V4 t
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。
    2 N; M1 _8 _. F% ]) k
    7 u/ {' z% o9 S& I5 ~

    ( d% U8 [% t' K# T6 }通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    8 c% \) J1 }! W9 l4 y
    : b" k- O& i$ O& g3 y% Q
    , A" @9 a- Z, k9 Q+ {, u
    8888.png
    + T, T4 U. o! m

    . g) T) N7 }2 C( q五、求next的算法, z; @0 F; k9 a
    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。: Z6 c+ ]) C! C' F

    : o! p) o6 C! r9 p( U( G

    $ G; b& O( L5 w$ ~0 lint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度! K! }5 l9 e+ R% K8 i9 I. m3 G
        next[1] = 0;
      o. Y$ F" n+ c# N4 f9 E  g    int i = 1,j = 0;
    $ C6 a7 q6 T! x$ w, |! p    while(i<=cLen){
    + g, k+ V8 \* _4 T        if(j==0||ch==ch[j]) next[++i] = ++j;
    ' [  E1 R6 |% J( \: e6 O$ I        else j = next[j];
    2 w3 V) t; a" P& m  g    }( p$ C6 Z5 s/ V# K0 n$ O
    }
    7 J# y3 q+ ~6 P! B- Y+ S5 d! i* @, i$ n- `
    还是先由一般再推优化:
    , Y6 P1 W- o) w8 c' p' D, y直接求next[j+1](至于为什么是j+1,是为了和下面的对应)9 Z  T6 p, I2 V8 s' L" a
    根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。1 v2 r8 g/ b) e4 N% T( O
    不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
    4 X) j: R: ]1 @$ ~2 A/ Cif(P1…Pj-1 == P2…Pj) => next[j+1]=j$ F1 K: f1 M. T! h' V1 k
    else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
    % G# E, ^/ H. I8 L4 r' I8 zelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2& @+ F% t" r' L" [+ y
    , P9 `4 L/ ?& L7 F7 ?* s

    4 {$ a) X! [2 h" V, f5 E8 a* V! o2 w' Y
    else if(P1P2 == Pj-1Pj) => next[j+1]=3
    ( b9 J  q: |8 Z9 t7 t( ]else if(P1 == Pj-1) => next[j+1]=2
    2 a. e  ]4 S0 u4 {" Aelse if(P1 != Pj-1) => next[j+1]=1
    ! G) A  _0 V2 \) A& c& J! M# G每次前去尾1个,后掐头1个,直至得到next[j+1]
    5 W5 u. \5 e0 ^/ Q. t; U
    . c) K9 ?5 U' \' h
    9 b" [" b; d# T
    再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。: {( \+ l$ Q" |8 W1 j3 l1 }3 g
    但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,% ]2 J9 |% {/ f) S' w1 D
    ①next[j+1]的可能的最大值是多少(即从哪开始验证)
    # c5 O4 {, ^" q$ B9 ~②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
    4 r) h# A! V  E看一下的分析:
    " R( O# I8 _: V& _' y% ^6 d- p- [* M+ @# w! e) S/ [
      S; ~2 t' U( a/ ?# Z5 L' a
    1、next[j+1]的最大值为next[j]+1。
    : `' @$ w2 E5 R5 i  h! I/ c4 |因为:! r8 h2 Y4 e8 \
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    + G& g, y# _, B% e如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+19 R! E7 N7 d! k; j9 h" _
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]* p( a6 t" U- @8 W% u  k
    这里不好解释,直接看下面的流程分析及图解
    + M: ^+ P" W# m
    : t  j# {: ]; i7 t

    8 w* j( U# k1 ~开——始——划——重——点!  P7 K( x  W8 t- r+ A4 r& T6 {3 w
    从头走一遍流程/ n' {$ F: H1 }3 C+ P! J5 A
    ①求next[j+1],设值为m
    ! ^$ t! G0 T& i- J8 O$ L②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-19 E( W! w2 x: A5 [! S
    ③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    8 j5 J1 c; c( y  c( O④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-11 [/ I/ D* r$ `1 ]( o( O
    ⑤第二第三步联合得到:
    2 j( c0 g% I# o- F% k# s& Z9 }. X0 e, QP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    $ F0 A5 y$ n; U; F0 K  k% d' ^⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推
    $ j. b0 f4 b/ ^* A; H
    % `* n4 V& S$ `1 X

    2 W- H8 |# W# a( x7 B# k上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    ) v) ]6 \2 J0 G: k# W1 c1、要求next[k+1] 其中k+1=174 e0 }' Z1 ^& H
    999.png
    0 b! H, j, p+ Y6 Q, L( `4 P

    7 i1 c) w# |- h8 e% k( y% v6 E2、已知next[16]=8,则元素有以下关系:- `3 s' D- n! J4 @3 Q) B
    10.png
    0 j) i% P$ g, h& V4 @, U
    2 t+ k2 Z: W$ {/ N1 w& X8 P4 w& d
    3、如果P8=P16,则明显next[17]=8+1=9- @+ k# ]. R! G/ {$ y( U; s0 a
    4、如果不相等,又若next[8]=4,则有以下关系9 {$ E% j+ y/ k: |% o

    2 E8 e6 W5 b1 F3 q( C# B
    11.png 6 X$ Y3 h8 v8 v
    又加上2的条件知
    ' i' M* j9 C& ?/ r9 g
    ! W% Z& s4 U; A' G+ V8 b. c
    12.png 3 V1 v) h) G- M
    主要是为了证明:0 D+ F' k7 P: D
    13.png
    9 l4 g. Q8 l; Y) s( H  [% k- _+ T, ^. [
    ' N  n0 X+ Q: C5 _
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    & `( w: u0 D9 G' f# U6、若next[4]=2,则有以下关系2 |# L$ J  l- L6 d6 e! U. Q5 W
    14.png
    " ]- v$ `* P6 W4 O8 x! x
    # ]* S% b. k8 J0 t8 M
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!1 a' Q. M* H4 @2 \+ V
    ————————————————- [+ C2 G$ s' N& I! j
    版权声明:本文为CSDN博主「Sirm23333」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。5 C% ?5 c' r- X) z
    原文链接:https://blog.csdn.net/qq_37969433/article/details/82947411
    ! v/ M8 |* D+ m( L9 W" v/ [3 T3 h2 P8 M! c, m: {$ @' [
    ' }4 L; y0 U' y4 D
    ; Y- B/ l! b0 G: h+ d( c" ?! r' g* ~" E
    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, 2025-7-29 00:56 , Processed in 0.386281 second(s), 54 queries .

    回顶部