QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2564|回复: 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值算法9 O) i1 J; k7 Q4 @

    4 n3 t1 E0 x: a' V8 g. e大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。
    3 l# e8 v( u; [0 Y4 G* ~! D8 @# P1 Y: }3 f4 n6 f( l; E2 e- R9 J% s
    " C! Z9 ^: n4 C- ?, }5 p
    本文的逻辑顺序为
    + o# c4 C+ O2 n5 z6 u9 b4 j7 H3 q1、最基本的朴素算法
    , D$ |5 O, H1 Y! s2、优化的KMP算法( x7 U- D+ v7 W: N
    3、应算法需要定义的next值, G' \. e# N( p! D, ^! J2 T
    4、手动写出较短串的next值的方法/ A7 u2 j# @+ r( o! z& X. S
    5、最难理解的、足足有5行的代码的求next值的算法
    - }( z+ E5 g, }0 Z所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…
    0 q( h; B# {' v& r
    7 G% B/ Q: z% j$ Y7 H% w- r2 V
    $ D5 ]+ Z1 x. ~3 t0 y) u8 l2 T% `7 k$ l
    一、问题描述
    * _5 B) w; ]2 v5 A2 F$ K给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。! W% j- U& I% y* z5 D3 W

    5 O- e+ R5 `, F' O. K; f' a
    1 Q. h) }  P9 Z+ I, E/ w
    二、朴素算法. p6 a- m7 L* w2 n
    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:& I/ V: r5 A$ ~8 E, Y  ?' p- ~
    1111.gif 7 l) Z5 m2 e) ?: j3 N* L1 z9 m

    # k( H8 x4 J) v+ j  s
    ( l5 p7 d/ o) L5 K9 o# h! b
    ! @/ N$ m4 c# u+ T
    这个算法简单,不多说,附上代码8 v, m- v( ~: r7 K& y% X; l/ V
    " m) p2 B5 ]* R; |

    : }* `. z$ Z) C( j$ A( u* I#include<stdio.h>. j: M8 ~5 c# E" \" S" c0 r1 L
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
    & j- c" M8 n# y    if(sLen<pLen)return 0;0 {' _9 q) s0 H; w
        int i = 1,j = 1;
    % |" a6 I4 E9 O$ e' ?" j  [  T    while(i<=sLen && j<=pLen){
    - P4 q5 l; F2 D1 i/ O% W) O1 j        if(s==p[j]){i++;j++;}
    ) J; \9 f0 f1 [0 |" h        else{, O4 \6 e) p) g. E
                i = i-j+2;% X* A+ p; e  m* O0 j1 N2 ]9 S% W
                j = 1;
    2 \$ c9 b# F' l2 N% Y& ~5 L6 `+ J' Z        }- q6 E/ z0 ^% a/ f: {- G
        }% s' \/ `+ c! |2 N
        if(j>pLen) return i-pLen;
    8 C  Z' w3 a) a! {5 K5 V) z    return 0;, I& a7 b4 G1 E7 i4 R- m
    }6 j' k5 O' F$ W% i
    void main(){
    ! e2 h3 r1 q# N0 q. H    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
    8 ^6 ^$ X( _' K* I# X    char p[]={' ','a','b','a','a','b','c','a','c'};
    1 L4 u, J+ V- I2 @# ]* V1 y- p- N    int sLen = sizeof(s)/sizeof(char)-1;
    8 o8 t3 o0 w6 M" E; {    int pLen = sizeof(p)/sizeof(char)-1;
    8 g) ~0 Q/ k' ~( W    printf("%d",Index_1(s,sLen,p,pLen));' E& k. [* u  q" q' [( K
    }; M9 ~2 J% }% q7 }* g4 k  l" m: X
    1  [8 z0 A8 J8 y2 Y7 n' p
    2% J1 [/ t0 E! m! ~
    3
    % @0 c) f* }6 ^4
    5 Q  K3 ~6 ^  d8 m. y! a: A& L5
    ( j; @3 D% h+ b. o3 A7 f6: s9 V4 l( [% _# R# f/ t9 g- m
    7
    5 D7 {2 r5 e+ @$ M; z" v$ H8
    + M$ Z. T9 }( P/ N. B9
    6 c/ ~" C& X  n5 X& h/ v108 R. ]+ D! Z- v. G8 f9 t
    11* j4 o& f4 d) U0 g  {: J2 x5 u+ A4 w
    12% C" q3 G. j& g+ d) R: B
    13
    # ]. Q  d  d/ I14' z( F  ?: N, ]. r
    15
    ) r  \1 s3 R, w' \( r3 E& ?! H16
    % B$ x3 a+ g- j2 E' T3 X17; P& D6 ?9 u" z4 l2 R# i9 _
    18* m# e: @) h$ N4 K7 S; h$ w/ L
    19
    4 J' E4 }" t7 A" C20$ d: V+ C3 N3 O: ^' _: R6 c; x, L
    211 Y, ?2 {" Q2 D5 H. d" j$ v% S
    三、改进的算法——KMP算法
    - A, Q$ ~7 O) x. n' |5 o, e朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    " h- v7 B) e- s+ q* @9 L4 B/ W: p! r0 m  ]一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    . j9 C% T2 U! V朴素算法中,P的第j位失配,默认的把P串后移一位。
    " B$ E+ F; t% T但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:1 @; l9 |3 ^* o+ O
    / `3 y' O( F" K* d: p
    222.gif * u$ Q6 O& Y3 w  J! d% Y" y

    0 a6 l! c. E" n+ \5 @

    4 F+ w$ A; V- l& [1 @" z: O这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。( D1 j' k( @# V% D, Y. e5 J' i8 }5 w

    / ~. K! p4 |( |6 _* D- E0 H
    + R* S( g3 f* k8 v4 s7 F, a, d
    相比朴素算法:
    8 Z+ x& \. [1 Q9 ^' p, p" @朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    " {- s6 t) M, W& E/ x, DKMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高
    1 h$ Z0 J( y/ R, @
    2 Z) \8 ^8 @: j; f; f

    4 Z& H' x2 J# g* s6 Y+ k而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)
    5 ?2 N7 {8 J( h4 s# \) \
    / L0 Q- K$ U4 T4 o
    7 N5 y- e2 Z' s9 c
    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)) [8 l7 \  [0 {0 K1 U( q9 S

    - w/ B, h, o8 t: h! k

    ; V* x' w: E* D* x) I+ r4 u比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
    5 i; w! u: N% H  j
    333.png
    # R* _/ `, u+ B$ s
    , U# `; [! c/ H4 v( o' A9 _

    6 Z- [* l: h! d4 c5 U8 i2 I假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”, i& G* A. o1 V6 j+ `( v1 z
    + n% n5 |& }% [. F$ ?; I1 U
    4444.png
    $ E1 Z* x# u) W- |- w1 ]& d9 T
    : s% U( D, r6 p; l. V7 ^3 v6 N0 [

    - t1 e" [; J; G" @* z+ m! c7 ~2 r那么可以推出,P1…Pk-1与Si…Si+j-2
    + d( ^0 v& G& @3 f2 S: N: x1 i8 A' ^  D' k3 Y/ R3 I! p2 e% b
    555.png
    % {- }& F) D4 h5 O6 U; Q. P0 S4 s# m( I6 U- ^7 ?

    5 z% J& T4 W/ q显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
    * M4 y- v+ T6 v- a/ u  B+ T; d# u' K; B+ L! m& N# z  j
    666.png
    ( ?  h+ x$ e. f% W! \/ d* o* W5 a; E" E  O" l5 S
    * s. I- \5 x$ C6 L
    为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。) w/ o6 n9 q6 f0 T" U% S

    $ {1 M8 ?5 H, G) B' \4 @9 X
    ) Y( f& v# Z# i) ~
    最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。
    6 |6 u, r7 k7 ]7 E$ L! y! g1 K: T; Y8 C" o6 E" D' V0 O
    ! d9 E  V# g9 t4 t/ n
    四、手动写出一个串的next值
    " L2 F& G5 A8 r3 y9 ~我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:  Y. B! L2 `  ~8 b6 i( C, n5 c3 u
    9 c+ T6 M9 |. [
    7777.gif % `+ O. P( M" V7 x/ P
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。# R* S% ?) L% W3 C! O
    : Y( P8 @8 o- ~3 f
    & D  ~* B9 \4 r- f- y7 e8 `. F
    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:6 }- }1 `- S8 I
    3 ]9 z" a, Q  D, e# q& W! c

    ! k' X# g2 S: l) o: f! M
    8888.png 3 c* z( f2 @6 Z  D
    % d4 q' E$ E# W/ V! z. z' S' e, V
    五、求next的算法
    $ [( U5 [4 z" ?& R3 h/ o6 m5 A终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。( z& e1 @2 v1 S7 c5 S' \* q7 @
    4 H, G' u( V/ }$ ]1 ]2 }, A; Z

    . O) s; @/ k3 v" a4 cint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度, ]% i5 T9 }" _: ]5 |7 X* t: V# ?
        next[1] = 0;' a4 ~: v- ^" o3 W' G9 v$ h
        int i = 1,j = 0;
    5 Z2 s4 Y5 J$ ?  x2 O  ]2 ]/ U6 F    while(i<=cLen){! L2 X: l: ^3 A2 \; }9 a, `
            if(j==0||ch==ch[j]) next[++i] = ++j;
    # `& w' c5 H. u1 c( M        else j = next[j];( Z) v, d+ b7 Q. }( M. P4 p6 r$ @
        }' V: q) M. ~! P+ _( E
    }/ ]- ^/ m, k( q4 l. r1 n0 c

    ( _4 l' u- V: o) Q* Q, p+ L8 Q/ z5 d还是先由一般再推优化:
    0 c6 ?+ W7 }) o+ l5 W9 ~直接求next[j+1](至于为什么是j+1,是为了和下面的对应)* ^6 f$ M6 R! L3 m2 X
    根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
    " w  y) ~5 d" A( r  [不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:2 N9 I  N  N3 u# T
    if(P1…Pj-1 == P2…Pj) => next[j+1]=j7 p0 h' P- c9 D
    else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-14 l2 @' u, I: _
    else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-20 ?9 ?+ [+ u8 q2 @
    + g+ C. m; J) O& w7 r# S) U; Q

    7 X" ^6 j0 C& C. l& G9 F; i, u, |/ K2 \% \4 |" W9 k" L2 V
    else if(P1P2 == Pj-1Pj) => next[j+1]=3
    7 S5 `( {% z% m9 p* R2 ~else if(P1 == Pj-1) => next[j+1]=2
    2 |( b: A! S+ X( J1 delse if(P1 != Pj-1) => next[j+1]=1
    ! l. b1 i' J& b2 R, R9 l4 B每次前去尾1个,后掐头1个,直至得到next[j+1]
      p, _" ~# s* q2 w% H& {9 |, ?0 G( M, m3 z9 r; s1 M
    ' u. ~- Z! }3 e( Y7 a. i
    再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。
    ' J: e! S/ |4 G( p1 ~* b, [2 x6 C但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,1 s2 F% N# ]4 \4 y% B
    ①next[j+1]的可能的最大值是多少(即从哪开始验证): y9 O( A0 U! w$ ^# Z
    ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)+ B5 v$ H# o1 T' `% X; L+ O
    看一下的分析:
    ' h3 }) i& ~  V% a! [* G: h7 J% `/ V  G$ \* l  k8 [
    : g- H. e& T( ^# i% t
    1、next[j+1]的最大值为next[j]+1。
    3 B' n$ u* d" O: b% ^因为:
    , o4 }' o0 K$ F" _- t" L假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。/ A& G- u* [( ^) b  P5 ]
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    + h/ k: }0 h8 o8 l/ j- |# b) m2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    * N  F" {" M6 N这里不好解释,直接看下面的流程分析及图解
    ; s6 w1 l+ s2 f6 K# W8 \! d+ N2 h' j/ m! y7 Q% J

      k) w1 \- K; ^  O% u6 l开——始——划——重——点!' d4 X" \7 V' s! R" h9 \
    从头走一遍流程$ x- h. i" L2 ^: [
    ①求next[j+1],设值为m
    ( [# Y* ^, F8 i$ P- ~# o+ [②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-18 ?; f6 Q0 b( s% |# U- ~
    ③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则  f6 C: F/ G  q# _" ^
    ④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    : n3 W) H1 q2 H: Y: ~- r, [' G' ?⑤第二第三步联合得到:2 t: `5 S4 g3 Q& Q  X: G' u
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合5 o: {7 ?; U  i1 T0 e: W# `- M6 R8 O
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推
      @6 J& T0 K4 R6 m3 t, O# o6 h$ _! \9 l

    ' s. c6 j! W9 A% d# U6 n1 ^: z2 Y上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1 p' R' b% Q0 ~8 j1、要求next[k+1] 其中k+1=17# D0 Z" e+ @" k+ g# M; U
    999.png
    2 Z$ f6 Q) e* C9 {$ _/ k0 P

    9 D  D' G$ D! E4 l+ X- p: U0 y2、已知next[16]=8,则元素有以下关系:
    : N; u+ t( q5 x- ]- Y8 t( d
    10.png + w$ J% A8 F& e1 x3 |4 x

    7 K! S  S* v- N: e" ~  I3、如果P8=P16,则明显next[17]=8+1=9: ~5 _5 N! e! r( I1 H0 c
    4、如果不相等,又若next[8]=4,则有以下关系
    ) `% U- M; g8 r9 J. E* G
    * S* z$ S5 @  l+ @8 M9 F4 q
    11.png 8 J7 e. f8 z0 B9 k
    又加上2的条件知. E" f7 x9 \/ }5 @; V2 \/ p3 l6 f

    3 S" c- \4 }  j1 a/ p
    12.png 4 A- u) F' I& N
    主要是为了证明:/ z( y% d; D2 K- g
    13.png
    . Z6 v* q* P2 Y2 H: m# }
    , j# i4 [9 E/ X) d$ |
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    : ~0 x$ F) {7 t3 W# `6、若next[4]=2,则有以下关系. x  k& m& s. r( F& `9 E( K2 M7 W
    14.png ( }, v+ ]- _8 t$ Z$ b

    6 d6 T- a  Z1 v8 _  e7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!4 e  X0 p% w% s: |2 _% B
    ————————————————/ u4 M% y1 j2 x/ @5 h- [( y( m
    版权声明:本文为CSDN博主「Sirm23333」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。+ M' x# o; v# [% o
    原文链接:https://blog.csdn.net/qq_37969433/article/details/82947411) h+ H+ F( a* m" |/ P6 [& V- V1 ?

    8 y8 M7 t4 n% g- Z( C7 }* z8 B  U# L4 B8 f
    ! }. F' Q( R* c, C
    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-24 10:48 , Processed in 0.563991 second(s), 53 queries .

    回顶部