在线时间 1630 小时 最后登录 2024-1-29 注册时间 2017-5-16 听众数 82 收听数 1 能力 120 分 体力 557309 点 威望 12 点 阅读权限 255 积分 172566 相册 1 日志 0 记录 0 帖子 5313 主题 5273 精华 18 分享 0 好友 163
TA的每日心情 开心 2021-8-11 17:59
签到天数: 17 天
[LV.4]偶尔看看III
网络挑战赛参赛者
网络挑战赛参赛者
自我介绍 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组 : 2018美赛大象算法课程
群组 : 2018美赛护航培训课程
群组 : 2019年 数学中国站长建
群组 : 2019年数据分析师课程
群组 : 2018年大象老师国赛优
(算法)通俗易懂的字符串匹配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 q 1、最基本的朴素算法
, D$ |5 O, H1 Y! s 2、优化的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- ~
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& L 5
( j; @3 D% h+ b. o3 A7 f 6 : s9 V4 l( [% _# R# f/ t9 g- m
7
5 D7 {2 r5 e+ @$ M; z" v$ H 8
+ M$ Z. T9 }( P/ N. B 9
6 c/ ~" C& X n5 X& h/ v 10 8 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/ I 14 ' z( F ?: N, ]. r
15
) r \1 s3 R, w' \( r3 E& ?! H 16
% B$ x3 a+ g- j2 E' T3 X 17 ; P& D6 ?9 u" z4 l2 R# i9 _
18 * m# e: @) h$ N4 K7 S; h$ w/ L
19
4 J' E4 }" t7 A" C 20 $ d: V+ C3 N3 O: ^' _: R6 c; x, L
21 1 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
* 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, D KMP算法: 每次失配,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
# 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
$ 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
% {- }& F) D4 h5 O6 U; Q. P 0 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
( ? 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 |. [
% `+ 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
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 c int 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]=j 7 p0 h' P- c9 D
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1 4 l2 @' u, I: _
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2 0 ?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 d else 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) m 2、如果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-1 8 ?; 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 m 3 t, O# o6 h$ _! \9 l
' s. c6 j! W9 A% d# U6 n1 ^: z2 Y 上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
1 p' R' b% Q0 ~8 j 1、要求next[k+1] 其中k+1=17 # D0 Z" e+ @" k+ g# M; U
2 Z$ f6 Q) e* C9 {$ _/ k0 P
9 D D' G$ D! E4 l+ X- p: U0 y 2、已知next[16]=8,则元素有以下关系:
: N; u+ t( q5 x- ]- Y8 t( d
+ w$ J% A8 F& e1 x3 |4 x
7 K! S S* v- N: e" ~ I 3、如果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
8 J7 e. f8 z0 B9 k
又加上2的条件知 . E" f7 x9 \/ }5 @; V2 \/ p3 l6 f
3 S" c- \4 } j1 a/ p
4 A- u) F' I& N
主要是为了证明: / z( y% d; D2 K- g
. 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
( }, v+ ]- _8 t$ Z$ b
6 d6 T- a Z1 v8 _ e 7、若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 }* z 8 B U# L4 B8 f
! }. F' Q( R* c, C
zan