QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2570|回复: 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值算法
    - }3 H% c3 a; d: W# H7 |
    ; D1 `1 c& g- [8 X7 w7 L& H- y大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。( E3 z9 a0 X: b1 O9 u- K" l
    9 h6 @8 d5 |, A, k, F) o

    $ v+ a! R& k0 N/ U本文的逻辑顺序为$ N8 J7 M6 B4 N1 ?2 ]; t3 `
    1、最基本的朴素算法7 p3 i; J: G* W; Q; f. x. [
    2、优化的KMP算法
    , t  n( h) F4 ~7 b; J) F3、应算法需要定义的next值
    # {' a2 x4 H4 J) @: g# ^4、手动写出较短串的next值的方法. ]# L6 b5 b) ]5 L5 y* T
    5、最难理解的、足足有5行的代码的求next值的算法: o8 D0 `7 i5 V8 d6 L
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…
    # o/ ~" \2 a6 h3 q+ F' D: n# N# n9 ~% w4 F) O' n

    7 Q4 {9 J' W+ A% J6 S' U一、问题描述
    ; B4 D" e) |2 H7 @7 e1 H! s! A给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。
    # L' o* i* L2 j. V: c
    % j6 o/ q6 Q$ q" m
    6 k0 A+ ]9 h- d( @8 \, c
    二、朴素算法4 P! x9 Y: F3 D( W# e& X4 `
    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:
    1 v% Q* L2 ^3 Y% m 1111.gif
    2 b8 D+ `. K8 ~" ?' b7 b# U' F

    3 p* ~6 c8 a: Z* L4 K
    # u- K; M5 O: ^& S7 M" Y0 [  L: N

    % _3 l0 K; {7 q- _! b) j这个算法简单,不多说,附上代码
    * w7 y2 s) R& G9 k" J- r3 x3 V6 [9 B6 ]8 G1 [

    , S+ B. w7 n/ P* T7 r& o8 K, Q#include<stdio.h>
    - H, ^/ w6 n5 K3 [# M5 a9 I0 n3 iint Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
    & W5 [* f9 ^. {2 J    if(sLen<pLen)return 0;  L4 Y% B( p1 v
        int i = 1,j = 1;
    6 A# E, g, P1 T# ?/ b2 M7 {( b# C    while(i<=sLen && j<=pLen){; {6 i9 h: e# @  s
            if(s==p[j]){i++;j++;}
    7 g7 I3 q! H* g# ?( h        else{
    9 T) T/ \3 }9 H" e! x            i = i-j+2;
    ; Z4 Y1 [9 `: c8 v            j = 1;' |2 U) J) m$ I$ o# R, [
            }' H% s8 w1 G6 D  K- s$ I/ M
        }9 ~( W* b; x& ~4 v1 b# k1 J+ _
        if(j>pLen) return i-pLen;
    . \2 Z( t; I5 C$ A    return 0;
    7 S) Z9 w) m2 D; b. K  I. m: m4 i+ y}0 e' ]8 W* v0 q" S4 S5 {
    void main(){- A4 b- K  l, @# e# H4 G" D. Q9 P
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
    , |6 Z! V- d- E/ w' B! M    char p[]={' ','a','b','a','a','b','c','a','c'};
    * g( E# l* p6 q$ q8 n  P! a! k    int sLen = sizeof(s)/sizeof(char)-1;
    , p2 t* H5 Y1 w% \( Q; c2 F$ H    int pLen = sizeof(p)/sizeof(char)-1;7 y, s+ P' r* E& O9 B! D  G+ n+ p
        printf("%d",Index_1(s,sLen,p,pLen));3 Q* g$ z( [3 |2 u
    }! h( x. U; q* P& x3 A
    1
    ; ?$ l) h- l  c9 \" o! I3 l, {% e2
    : _9 x& M4 {$ X' P5 u3% x. W- `9 e$ F, l  @1 t
    4
    2 n. _% R' N) ^5+ _9 d1 ?0 y, T) g" }
    62 Y& l- _4 s' a* L! W1 W4 ^
    7
      J3 f5 {. ]( ~3 b$ ?8  n, ]; _4 A8 n/ z% A; X
    9
    # N- ^# F( F9 M& o10
      J" v' x, ^: J) ^11
    ( |' O. c4 a8 G# D: F  l* O& w12& K  u5 T' s! p* F/ `
    13
    3 P, @% b1 m. [; E1 w* u" I14) I/ ^. ~3 x9 r# v* E, a
    15
    2 j4 B' `& F$ I: A6 ?16; B! e0 d8 ?! ?+ @
    175 i" f) s2 Z/ N( O
    18  k8 c* w, \* O; v- v1 K# |. {
    19
    0 e9 k* s5 n# C7 S% O# b% e  }, i20. j6 x$ Z$ h$ h. c* U5 t
    21
    ) m' R/ k0 T& f, w三、改进的算法——KMP算法
    0 |, b, D% Y3 Q1 K$ d- T: s朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。* B2 r$ d4 |( _! h5 M( M; b5 ]
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。, S- h2 c" q4 Z( E
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    1 x/ [+ k" B8 d5 Q) R( J( [) n但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:/ a+ s: m1 X; @$ u
    ; X! Y( v$ _* Y" ]# s6 ?
    222.gif
    , T% t4 v  I9 w4 C5 B' I0 W" H" ]- t' o! s% `0 D6 U9 d
    ' _: p1 I( J4 y) J
    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。9 U0 l7 e  c$ Z+ Q* F% ?% g

    7 f; }. r. e1 b& k& w

    2 k  A6 v( Y5 Z3 S8 Y3 k相比朴素算法:
    ' Y1 A; z0 d- {9 G# x( p5 W0 G" R朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)* x9 Q+ T4 _9 K: k3 W! X" f9 O7 U$ f+ b
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高
    7 c! X5 |/ ]0 w0 W5 A7 @. X
      d4 t" t5 _# ]* O4 X

    2 x, F9 [+ T8 Q! S4 y, `" m而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)7 [! f/ b# ?3 O+ {
    3 P: g! K) Z) W4 }, u) I/ u0 R4 [

    7 y; `' J" T) E$ H: S开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)0 s/ I/ y6 [8 V% \
    5 C0 h& P. ?: ^- E" `8 {7 n
    8 U0 \! i; J/ {5 O2 J2 }0 ?
    比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
    4 K/ H" R, c$ V# c
    333.png
    ' O0 y/ ?  M8 ^" L# ?" D  O& n1 ?) W% y% c1 S
    / n2 S# w6 f) k: @* P; Z
    假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”+ q* s; s1 q$ H, Y& H/ w) P

    ; S$ q. b( q5 ~  i
    4444.png
    " M1 }" r. ]' ^% C8 I5 M+ L
    * f6 h+ L" i0 ^

    . e' c0 u" q, U" W3 m那么可以推出,P1…Pk-1与Si…Si+j-2! K+ S2 d! j7 u$ ]/ i( M9 J

      m" Q2 Q# Y2 k! O, |+ ]
    555.png
    3 ^2 _) ?$ h2 u, ~! w, v  _2 z; `/ t0 W# p( l$ W7 L) S
    8 K: r9 T. V: G- |6 ~
    显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:2 [4 K" U# {$ i' F* ]

    5 A7 {( Y$ A/ _9 T0 @! H0 n
    666.png
    ( ]5 x! ^' `0 U
    8 O; _- z  X: Q. b! j% a& b
    - O- Y- T# U9 }+ A
    为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。$ t( G! C, x" g/ `' d% o
    - B$ ^0 H3 Y# n4 G) @; r' g# s

    : \. \3 z9 }, m3 v最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。
    * J, b) r( C+ f  l6 @# u* Z# N, s% @% _* z7 l
    5 t0 J' d: }, U/ \! M/ o
    四、手动写出一个串的next值
    7 Z) U" X! t, `我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    4 I% e& b8 v; i
    9 O. x: f5 Q# `* k% k5 j' L' {
    7777.gif # k7 ~; e( o, v6 d" L/ C: g
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。
    ; E' H) G( U) R& z5 m
    + U" J  h+ a: B5 D0 M1 X$ r
    ' e3 Q3 \) V4 P1 R( e0 L1 q
    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:* `. {/ V. [# P! y* C9 x1 c! {

    , h) O6 R3 Q$ q8 A0 A7 ?! e
    ( B( P' m' y* V3 W3 F8 ?
    8888.png * V1 _+ e% I' E0 V/ ^
    2 u% j; b3 e# z% N
    五、求next的算法# I6 t; [0 L6 Q' a
    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。
    & v+ N# G0 v1 K) N5 b! x; A& u: b7 x) j. j& O3 n0 w6 T/ M; S

    & E9 H6 s1 [" {% q: q( o' o8 Kint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度: t' W2 S% J; ^& ?, w# Y1 _; c) x
        next[1] = 0;
    ) Q- @  j: z' z/ V/ T    int i = 1,j = 0;7 j7 r+ M% `) A& x" U
        while(i<=cLen){
    ( ~& R6 z, Q. j! c  W; D  F        if(j==0||ch==ch[j]) next[++i] = ++j;9 H. |. l$ G( `8 v; U% O7 D
            else j = next[j];+ B9 t! G4 }: X' S1 \# n
        }- T( t: t: {) F1 |' m, j4 L
    }
    . I1 ~$ G" m, e1 G! G* N; N& L( G
    & i& R! o" Q1 I& o还是先由一般再推优化:
    ! x3 U4 T9 A9 T, `直接求next[j+1](至于为什么是j+1,是为了和下面的对应)1 d2 e+ L  |9 J* c1 }; [) v
    根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。5 H- U: n# y4 s
    不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:' {' h  j- t$ L. c
    if(P1…Pj-1 == P2…Pj) => next[j+1]=j
    , l' B( h- z1 ^2 {; D: w- Oelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
    / G( s& J0 M- D7 uelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2/ H/ q2 w9 }: L7 s! D6 g+ e/ N9 ]
    " W1 @  A4 y# Z. a
    4 L* C. _) F3 S& t0 n& h

    / L) \( ?+ ~. `$ |: P9 T( u- Selse if(P1P2 == Pj-1Pj) => next[j+1]=3, K" Q. R& I" L  z1 |# J
    else if(P1 == Pj-1) => next[j+1]=2
    % {0 ?. i+ ^5 e# q2 B$ _) Lelse if(P1 != Pj-1) => next[j+1]=1
    + D% G) j3 A" T3 E  S) E9 q每次前去尾1个,后掐头1个,直至得到next[j+1]
    - Z3 Z0 u! ?+ t2 s4 L* H3 P; P9 v' W& U! j, o0 }2 z) B

    7 M; J# h3 h- ]* W1 v1 M9 e' B再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。
    8 y. Y. K0 l3 ~" D3 c. k但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
    2 f2 f/ f2 M1 G- \3 ?7 n+ G①next[j+1]的可能的最大值是多少(即从哪开始验证)
    + o0 v: _8 ?" F+ l7 D' L& S2 j* y②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
    ) p  `8 z, w  B  H$ I' y1 |7 P看一下的分析:4 o1 Z1 D3 Y7 p- w% @5 ?
    & r% k( ?* w/ z7 ^# A& p6 s+ n8 \
    : c: d9 n6 f' B2 U7 F$ G- K
    1、next[j+1]的最大值为next[j]+1。
    ) S6 _) M; E$ X8 b4 v因为:
    4 D  {( r7 H- w9 B假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    5 a4 f) e  W; v& u% }3 @如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    & U3 [( q* o! ^# v1 V, k: M2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]* E$ K* i5 S4 u  z0 ?3 |4 [
    这里不好解释,直接看下面的流程分析及图解4 Z6 n' b  `: @+ }
    8 u% h/ [/ U. }2 u, [. q

      g7 c3 ?3 {( p开——始——划——重——点!
    8 C: u* J+ b4 F. V$ z# }+ s从头走一遍流程7 t! ?. Q0 l1 l, b
    ①求next[j+1],设值为m
    / }/ s5 E9 g% }3 h5 F②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1# e3 X/ l; A6 ]8 E3 m7 a
    ③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则/ |3 z. n" h# q
    ④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    7 K- m/ b3 R+ C$ H. R( J1 q⑤第二第三步联合得到:
    1 e6 m7 u4 I: E8 C0 X! }% jP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    * ~2 O1 M  m1 Z/ R5 L/ r+ z⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推
    ! D  M7 K# @6 G7 {/ O* f
    ! J3 ?. F4 B8 d; S4 \
    * y* y9 {1 L) {
    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    ( U/ F) d6 O1 J# |5 |1、要求next[k+1] 其中k+1=17
    * O$ _' i- u$ u5 d) ?
    999.png : X/ _/ x: q( }1 z/ r) S

      E% E9 d4 {5 C# `- J: r1 _$ [. U/ w2、已知next[16]=8,则元素有以下关系:; d/ o/ ]- a* _4 V$ \  w. v% L# c
    10.png 8 A# i  {. A6 E, I# g; g2 @
    4 g% J) }; B6 {' H, B/ J- T& Z& E
    3、如果P8=P16,则明显next[17]=8+1=9
    & _2 j9 b* ]1 i' Y4、如果不相等,又若next[8]=4,则有以下关系
    5 c( }3 I2 l3 z( c% ?
    % M4 H" h3 h% u9 s
    11.png
    5 |& k/ a# Q2 M0 \1 q! l: v' ?1 N又加上2的条件知4 _1 r/ Z  z: ~3 d' z- H- c1 f
    " K# c4 a4 L& Y8 s
    12.png 2 N  ?9 W/ E+ R* S' p
    主要是为了证明:
    6 n( b# l. R# ~0 I; |# N& ^
    13.png # e. p9 m( }, t/ z* |

    2 ~' n+ N7 V) x. D. ]5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推6 G4 S+ z4 Q8 w0 j: t
    6、若next[4]=2,则有以下关系  j6 m" a: q6 R4 S: [7 s% a. w
    14.png   i2 D7 O% b! j) \8 b) c& ~# a

    2 m1 Z0 I# \) p7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!$ r* F6 [9 j9 x, d& B; P
    ————————————————' d% _" z  p6 }9 J
    版权声明:本文为CSDN博主「Sirm23333」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ( |; Y# z) W$ B原文链接:https://blog.csdn.net/qq_37969433/article/details/82947411( @  S# ^; G! Y

    : j/ F: U, Y, ?; G& n, y! s0 _8 V3 v
    8 F5 O$ b6 Q9 g# P% o! a3 P
    8 V$ ~8 {9 e/ y0 l
    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-25 15:44 , Processed in 0.338262 second(s), 53 queries .

    回顶部