KMP 字串搜寻演算法
[i=s] 本帖最后由 nwm310 于 2020-10-11 11:11 编辑 [/i]注意事项:
[b]-eq[/b] 不区分大小写。如果有需要,请改用 [b]-ceq[/b]
[table=98%,#012456]
[tr][td][font=monospace][size=12px][color=#dddddd]PS C:\> 'a' -eq 'A'
True
PS C:\> 'a' -ceq 'A'
False
[/color][/size][/font][/td][/tr]
[/table]
在 $Text 里面找 $Key ( 1个字 )
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'B'[/color]
[color=#c586c0]for[/color] ( [color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color] ; [color=#9cdcfe]$base[/color][color=#d4d4d4]++[/color] ){
[color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color]] ){ [color=#c586c0]break[/color] }
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Text.Length[/color]){
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]
在 $Text 里面找 $Key ( 2个字 or 2个字以上)
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]
[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#c586c0]for[/color] ( [color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color] ; [color=#9cdcfe]$base[/color][color=#d4d4d4]++[/color] ){
[color=#c586c0]for[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){
[color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] }
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]
把 第一层 for 改成 while
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]
[color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] [color=#7ca668]# edit 1[/color]
[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#c586c0]while[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color]){ [color=#7ca668]# edit 2[/color]
[color=#c586c0]for[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){
[color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] }
[color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#b5cea8]1[/color] [color=#7ca668]# edit 3[/color]
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table] [i=s] 本帖最后由 nwm310 于 2020-10-11 12:26 编辑 [/i]
KMP 字串搜寻演算法 - 如何移动?
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][b][color=cyan]一开始就比对失败:[/color][/b]
比对 移动后
[color=#9cdcfe]$i[/color] 01234567 01234567
Q[b][color=#ff00ff]B[/color][/b]AQABAB QB[b][color=#ff00ff]A[/color][/b]QABAB
X
ABAB ABAB
[color=#9cdcfe]$j[/color] 0123 0123
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
一开始就比对失败,此时的 [color=#9cdcfe]$j[/color] 是 0
看到 [color=#9cdcfe]$j[/color] 是 0,就移动1格。
移动1格的方法: [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color] 、 [color=#9cdcfe]$j[/color] 不变(仍是0)
[b][color=cyan]比对成功几字之后,然后才比对失败:[/color][/b]
比对
[color=#9cdcfe]$i[/color] 01234567
ABA[b][color=#ff00ff]Q[/color][/b]ABAB
|||X
ABAB
[color=#9cdcfe]$j[/color] 0123
[color=#b5cea8]1.[/color]在 [color=#9cdcfe]$j[/color] 索引3比对失败
[color=#b5cea8]2.[/color]前面3个字是相同的,「相同区」长度为3,内容为ABA
[color=#b5cea8]3[/color].「相同区」长度 [color=#d4d4d4]=[/color] 比对失败索引值([color=#9cdcfe]$j[/color])
如果在索引1比对失败,那麽「相同区」长度就是1
如果在索引2比对失败,那麽「相同区」长度就是2
[color=#b5cea8]4.[/color]在「相同区」里面找移动之后的「次相同区」(上下要相同)
移动前 移动后 错误移法(上下不同)
ABA ABA ABA
ABA ABA ABA
「次相同区」长度为1,内容为A
移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
[color=#d4d4d4]=[/color] 3 [color=#d4d4d4]-[/color] 1
[color=#d4d4d4]=[/color] 2
移动前 移动后
[color=#9cdcfe]$i[/color] 01234567 01234567
ABA[b][color=#ff00ff]Q[/color][/b]ABAB ABA[b][color=#ff00ff]Q[/color][/b]ABAB
|||X |
ABAB ABAB
[color=#9cdcfe]$j[/color] 0123 0123
比对失败位置 继续比对位置
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color] [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color]
移动2格之后,并且跳过1格不比对
「次相同区」长度,等於「跳过不比对」的长度
原本比对失败的 旧[color=#9cdcfe]$j[/color] 为3
即将参与比对的 新[color=#9cdcfe]$j[/color] 为1
新[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] 「次相同区」长度
知道「次相同区」长度,就可得知 新[color=#9cdcfe]$j[/color]
[b][color=cyan]下次比对时,参与比对的 [color=#9cdcfe]$i[/color] 没变(仍和上次一样)[/color][/b]
[b][color=cyan]但 [color=#9cdcfe]$j[/color] 变小了,藉此达成「右移」的效果[/color][/b]
因为 [color=#9cdcfe]$i[/color] 没有变、不会向后退:
可以不使用 [color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color] 的方式来取得 [color=#9cdcfe]$i[/color]
不再关注「移动几格」
而是关注「次相同区」长度
普通移法的 [color=#9cdcfe]$i[/color] 会向后退:
[color=#9cdcfe]$i[/color] 移动前 移动后
01234567 01234567
ABA[b][color=#ff00ff]B[/color][/b]AQABAB A[b][color=#ff00ff]B[/color][/b]AQABAB
|||X
ABAB ABAB
[color=#9cdcfe]$j[/color] 0123 0123
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color] 比对失败 从 [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color] 继续比对。
[color=#9cdcfe]$i[/color] 改变了、向后退了
[color=#b5cea8]5[/color].「相同区」长度为1,「次相同区」长度一定是0
移动前 移动后
A A
A A
长度太短,无法去找「次相同区」
「次相同区」长度为0
移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
[color=#d4d4d4]=[/color] 1 [color=#d4d4d4]-[/color] 0
[color=#d4d4d4]=[/color] 1
[color=#b5cea8]6.[/color]别的例子
移动前 移动后 错误移法(上下不同)
ABB ABB ABB
ABB ABB ABB
「相同区」长度为3
「次相同区」长度为0
移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
[color=#d4d4d4]=[/color] 3 [color=#d4d4d4]-[/color] 0
[color=#d4d4d4]=[/color] 3
移动3格之后,即将参与比对的索引值[color=#9cdcfe]$j[/color] 为0
[color=#9cdcfe]$j[/color] 等於 「次相同区」长度
[color=#b5cea8]7.[/color]别的例子
移动前 移动后 错误移法(上下不同)
ABAA ABAA ABAA
ABAA ABAA ABAA
「相同区」长度为4
「次相同区」长度为1
移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
[color=#d4d4d4]=[/color] 4 [color=#d4d4d4]-[/color] 1
[color=#d4d4d4]=[/color] 3
移动3格之后,可以跳过1格不比对
「次相同区」长度,等於跳过不比对的长度
即将参与比对的索引值[color=#9cdcfe]$j[/color] 为1
[color=#9cdcfe]$j[/color] 等於 「次相同区」长度
[color=#b5cea8]8.[/color]别的例子
移动前 移动后 错误移法(上下不同)
ABAB ABAB ABAB
ABAB ABAB ABAB
「相同区」长度为4
「次相同区」长度为2
移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
[color=#d4d4d4]=[/color] 4 [color=#d4d4d4]-[/color] 2
[color=#d4d4d4]=[/color] 2
移动2格之后,可以跳过2格不比对
「次相同区」长度,等於跳过不比对的长度
即将参与比对的索引值[color=#9cdcfe]$j[/color] 为2
[color=#9cdcfe]$j[/color] 等於 「次相同区」长度
[/color][/size][/font][/td][/tr]
[/table]
KMP 字串搜寻演算法 - $base 「移几格」版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#7ca668]<#[/color]
[color=#7ca668] $f 是一个数组,它的长度和 $Key 一样[/color]
[color=#7ca668] 索引值 为 比对失败位置(也等於相同区长度)[/color]
[color=#7ca668] $f[ 比对失败位置 ] 得到 「次相同区」长度[/color]
[color=#7ca668] $f[ 旧$j ] 得到 新$j[/color]
[color=#7ca668] $f[0] = -1 这个值在本程式里不会使用到[/color]
[color=#7ca668] $f[1] = 0 相同区长度是 1 次相同区长度一定是 0[/color]
[color=#7ca668] 此处设定 $f数组 其他元素内容[/color]
[color=#7ca668]#>[/color]
[color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color]){
[color=#c586c0]for[/color] ( ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){ [color=#7ca668]# 这里没有设定 $j 的初始值[/color]
[color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] } [color=#7ca668]# 找到了[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]0[/color]){[color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#b5cea8]1[/color]; [color=#c586c0]continue[/color]} [color=#7ca668]# 一开始就比对失败[/color]
[color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#7ca668]# 移几格? 「相同区」长度 - 「次相同区」长度[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#7ca668]# 设定 新$j 。 「次相同区」长度、用来跳过不比对[/color]
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]
KMP 字串搜寻演算法 - 「$i vs $j」版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#7ca668]<#[/color]
[color=#7ca668] $f 是一个数组,它的长度和 $Key 一样[/color]
[color=#7ca668] $f[旧$j ] 得到 新$j[/color]
[color=#7ca668] 此处设定 $f 元素内容[/color]
[color=#7ca668]#>[/color]
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$i[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color]){ [color=#7ca668]# 此处和前例不同[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]){ [color=#7ca668]# 比对成功[/color]
[color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#7ca668]# 找到了[/color]
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]-[/color] [color=#9cdcfe]$j[/color] [color=#7ca668]# 注意:要用减法[/color]
[color=#c586c0]break[/color]
}
}[color=#c586c0]else[/color]{
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){ [color=#7ca668]# 有「相同区」[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#7ca668]# 以「次相同区」长度 设定 新$j。[/color]
[color=#7ca668]# $i 不变[/color]
}[color=#c586c0]else[/color]{[color=#7ca668]# 一开始就比对失败。$j是0、不用设定[/color]
[color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
}
}
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$ans[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]-1[/color]){ [color=#7ca668]# 此处和前例不同[/color]
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$ans[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table] $f[ ] 的种类
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][b][color=cyan]第一种:[/color][/b]
[color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] ] 得到 「下次比对位置」
[color=#9cdcfe]$f[/color][ [color=#569cd6]相同区长度[/color] ] 得到 「次相同区长度」
找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
要继续找下一个符合的 [color=#9cdcfe]$Key[/color],
不可以用 [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] 得到 新[color=#9cdcfe]$j[/color] (下次比对位置)
因为 [color=#9cdcfe]$j[/color] 超出索引值范围
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
本篇教学使用这种
[b][color=cyan]第二种:[/color][/b]
[color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 「下次比对位置」
[color=#9cdcfe]$f[/color][ [color=#569cd6]相同区的最后1个索引值[/color] ] 得到 「次相同区长度」
找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
要继续找下一个符合的 [color=#9cdcfe]$Key[/color],可以用:
[color=#9cdcfe]$f[/color][ [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 新[color=#9cdcfe]$j[/color] (下次比对位置)
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[b][color=cyan]第三种:[/color][/b]
[color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 次相同区的最后1个字的索引值
[color=#9cdcfe]$f[/color][ [color=#569cd6]相同区的最后1个字的索引值[/color] ] 得到 次相同区的最后1个字的索引值
如果没有次相同区,得到 [color=#b5cea8]-1[/color]
找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
要继续找下一个符合的 [color=#9cdcfe]$Key[/color],可以用:
[color=#9cdcfe]$f[/color][ [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 次相同区的最后1个字的索引值
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[/color][/size][/font][/td][/tr]
[/table]
如何得知 $f[ ] 是哪一种?
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd]1.确认 [color=#9cdcfe]$j[/color] 的意思
观察「比对时的程式码」
例如:[color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] -eq [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]
确认 [color=#9cdcfe]$j[/color] 是不是「参与比对的索引值」
2.查看 [color=#9cdcfe]$f[/color][ ] 的使用情形
如果 [color=#9cdcfe]$j[/color] 是「参与比对的索引值」
第一种: [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]
第二种: [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color] - 1]
第三种: [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color] - 1] + 1
[/color][/size][/font][/td][/tr]
[/table]
在「相同区」里找「次相同区」
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Key[/color] = [color=#ce9178]'ACAQACACQ'[/color]
各种长度 的「相同区」
长度 寻找范围 移动后 次相同区长度 ([b][color=cyan]$len[/color][/b])
6 A[b][color=cyan]CAQAC[/color][/b] ACAQ[b][color=cyan]AC[/color][/b] [b][color=cyan]2[/color][/b]
ACAQAC [b][color=cyan]AC[/color][/b]AQAC
确认是否可以沿用长度6的起点
7 A[b][color=cyan]CAQACA[/color][/b] ACAQ[b][color=cyan]AC[/color][/b][b][color=#ff00ff]A[/color][/b]
ACAQACA [b][color=cyan]AC[/color][/b][color=#ff00ff]A[/color][/b]QACA
长度越长,次相同区的寻找范围就越长
「次相同区」的起点,不需要从「寻找范围」的最左边找起
「长度7」比「长度6」多1字
用多出来的那1字,即「长度7的最后1字」
去比对 [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]
确认「长度7」的次相同区,是不是「长度6」的次相同区「加长版」
它们「次相同区」起点是不是一样的
如果它们「次相同区」起点是一样的
「长度7的[color=#9cdcfe]$len[/color]」等於「长度6的[color=#9cdcfe]$len[/color]」加[b][color=cyan]1[/color][/b]
---
长度 寻找范围 移动后 次相同区长度 ([b][color=cyan]$len[/color][/b])
7 A[b][color=cyan]CAQACA[/color][/b] ACAQ[b][color=cyan]ACA[/color][/b] [b][color=cyan]3[/color][/b]
ACAQACA [b][color=cyan]ACA[/color][/b]QACA
确认是否可以沿用长度7的起点
8 A[b][color=cyan]CAQACAC[/color][/b] ACAQ[b][color=cyan]ACA[/color][/b][b][color=red]C[/color][/b]
ACAQACAC [b][color=cyan]ACA[/color][/b][b][color=red]Q[/color][/b]ACAC
「长度8」[b][color=cyan]不可以[/color][/b]沿用「长度7」的起点
[b][color=cyan]在长度7的「次相同区」里面移动、寻找「次次相同区」[/color][/b]
ACA AC[b][color=cyan]A[/color][/b]
ACA [b][color=cyan]A[/color][/b]CA
把长度7的「次相同区长度」 ([color=#9cdcfe]$len[/color] 其值为 3)
当作$f[]的索引值
得到 新[color=#9cdcfe]$len[/color]
即 [color=#9cdcfe]$len[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
新[color=#9cdcfe]$len[/color] = [color=#9cdcfe]$f[/color][3] = 1
[b][color=cyan]不可以[/color][/b]沿用「长度7」的起点
ACAQ[b][color=cyan]ACA[/color][/b][b][color=red]C[/color][/b]
[b][color=cyan]ACA[/color][/b][b][color=red]Q[/color][/b]ACAC
确认是否可以沿用「新起点」 以「长度8的最后1字」比对 [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]
ACAQAC[b][color=cyan]A[/color][/b][b][color=#ff00ff]C[/color][/b]
[b][color=cyan]A[/color][/b][b][color=#ff00ff]C[/color][/b]AQACAC
如果新起点ok:
「长度8」的次相同长度,等於 新[color=#9cdcfe]$len[/color] 加 1
如果新起点不ok:
如果新$len不为0,就再一次[color=#9cdcfe]$len[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
重复上述动作
如果新$len已经是0,就不用再 [color=#9cdcfe]$len[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
「长度8」的次相同长度,就是0
[/color][/size][/font][/td][/tr]
[/table] 设定 $f[ ]
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#7ca668]# $f[相同区长度] 得到 「次相同区」长度[/color]
[color=#7ca668]# $f[旧$j] 得到 新$j[/color]
[color=#7ca668]# KMP 只有在 $Key长度大於等於 3 才会比普通找法快[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}
[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color] [color=#7ca668]# $j 是相同区长度。它大於等於2,才可以去找「次相同区」[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#7ca668]# 把 「相同区长度1」的「次相同区长度」,存到 $len[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){[color=#7ca668]# $j 是比对失败位置,它小於 $Key.Length[/color]
[color=#7ca668]# 现在要从「相同区」里面,找「次相同区」[/color]
[color=#7ca668]# 「相同区」里有许多位置,可能是「次相同区」的起点[/color]
[color=#7ca668]# $j的「相同区」长度,比 ($j-1) 「相同区」长度多1[/color]
[color=#7ca668]# 如果 ($j-1)相同区内的某位置,不能当作「次相同区」起点[/color]
[color=#7ca668]# 那麽 $j相同区 也不能使用那个位置,来当作「次相同区」起点[/color]
[color=#7ca668]# 於是,我们不从$j「相同区」里的最左边开始找起[/color]
[color=#7ca668]# 而是从($j-1)「次相同区」的起点开始找「次相同区」[/color]
[color=#7ca668]# $f[$j-1]是 ($j-1)的「次相同区」长度,等於 $len[/color]
[color=#7ca668]# $len 是($j-1)「次相同区」长度,不是起点[/color]
[color=#7ca668]# ($j-1)的「次相同区」内容为 $Key[0] 到 $Key[$len-1][/color]
[color=#7ca668]# $j相同区 比 ($j-1)相同区多1字[/color]
[color=#7ca668]# 用 「$j 相同区的最后1个字」 比对 $Key[$len][/color]
[color=#7ca668]# 来确定此起点是否合适[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){ [color=#7ca668]# ($j-1)「次相同区」起点合适[/color]
[color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}[color=#c586c0]else[/color]{ [color=#7ca668]# ($j-1)「次相同区」起点不合适[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
[color=#7ca668]# ($j-1)的「次相同区长度」不等於0[/color]
[color=#7ca668]# 那麽就在($j-1)「次相同区」里面[/color]
[color=#7ca668]# 寻找「次次相同区」的「起点」[/color]
[color=#7ca668]# 把「次相同区长度」作为 $f[]的索引值[/color]
[color=#7ca668]# 取得「次次相同区」长度[/color]
[color=#7ca668]# 这里并没有去改变 $j 的值[/color]
[color=#7ca668]# 在while的新一回合[/color]
[color=#7ca668]# 会测试 $Key[$j-1] -eq $Key[次次相同区长度][/color]
[color=#7ca668]# 确认「次次相同区」的「起点」是否合适[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
}[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]
[color=#7ca668]# 可能1:[/color]
[color=#7ca668]# ($j-1)的次相同区长度是0 [/color]
[color=#7ca668]# $j 相同区 的最后1字 不等於 $Key[0][/color]
[color=#7ca668]#[/color]
[color=#7ca668]# 可能2:[/color]
[color=#7ca668]# ($j-1)的次相同区长度不是0[/color]
[color=#7ca668]# 但「次次相同区」or「次次次相同区」or 「次次次次相同区」是0[/color]
[color=#7ca668]# $j 相同区 的最后1字 不等於 $Key[0][/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}
}
}
[/color][/size][/font][/td][/tr]
[/table]
预先知道:移动后,马上就比对失败
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd]
比对 移动后
[color=#9cdcfe]$i[/color] 0123456789 0123456789
AACAA[b][color=#ff00ff]Q[/color][/b]AACAAC AACAA[b][color=#ff00ff]Q[/color][/b]AACAAC
X X
AA[b][color=#ff00ff]C[/color][/b]AA[b][color=#ff00ff]C[/color][/b] AA[b][color=#ff00ff]C[/color][/b]AA[b][color=#ff00ff]C[/color][/b]
[color=#9cdcfe]$j[/color] 012345 012345
比对失败位置: [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] 5
「相同区」:AACAA
「次相同区」:AA
「次相同区」长度:2
如果「次相同区」后面的字,和比对失败位置的字相同
即,如果 [color=#9cdcfe]$Key[/color][[color=#b5cea8]2[/color]] 等於 [color=#9cdcfe]$Key[/color][[color=#b5cea8]5[/color]]
移动后的第一次比对,马上就比对失败
[/color][/size][/font][/td][/tr]
[/table]
设定 $f[ ] 改良版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}
[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]]
[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
[color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){ [color=#7ca668]# ok[/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]
}[color=#c586c0]else[/color]{ [color=#7ca668]# 移动后,马上就比对失败[/color]
[color=#7ca668]#在制表时,就先设定到最适合的次相同区长度[/color]
[color=#7ca668]#避免正式比对时,多做额外的比对[/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
}
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}[color=#c586c0]else[/color]{
[color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
}[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}
}
}
[/color][/size][/font][/td][/tr]
[/table] KMP 字串搜寻演算法 - 最终版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]
[color=#7ca668]#======= 设定 $f[] ========[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}
[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]]
[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
[color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]
}[color=#c586c0]else[/color]{
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
}
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}[color=#c586c0]else[/color]{
[color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
}[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]
[color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
}
}
}
[color=#7ca668]#======= 开始寻找 ========[/color]
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$i[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color]){
[color=#c586c0]if[/color] ([color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]){
[color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
[color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]-[/color] [color=#9cdcfe]$j[/color]
[color=#c586c0]break[/color]
}
}[color=#c586c0]else[/color]{
[color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]
}[color=#c586c0]else[/color]{
[color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
}
}
}
[color=#c586c0]if[/color] ([color=#9cdcfe]$ans[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]-1[/color]){
[color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
[color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$ans[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table] 字符串有indexOf方法查找索引, 可以简化代码, 省掉循环
页:
[1]