- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 557369 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 172584
- 相册
- 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值算法
- }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" m6 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
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 ?
, 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
' 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
" 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, |+ ]
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
( ]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' {
# 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 ?
* 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) ?
: 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
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
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
2 N ?9 W/ E+ R* S' p
主要是为了证明:
6 n( b# l. R# ~0 I; |# N& ^
# 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
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 P8 V$ ~8 {9 e/ y0 l
|
zan
|