[原创教程] KMP 字串搜寻演算法

nwm310

注意事项：
-eq 不区分大小写。如果有需要，请改用 -ceq

PS C:\> 'a'  -eq  'A' True PS C:\> 'a'  -ceq  'A' False

在 $Text 里面找 $Key ( 1个字 )

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'Ｂ' for ( $base = 0 ; $base -lt $Text.Length ; $base++ ){     if ( $Key -eq $Text[$base] ){ break } } if ($base -eq $Text.Length){     '没找到' }else{     "$Key 在 $base" }

在 $Text 里面找 $Key ( 2个字 or 2个字以上)

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'ＡＢＡＢ' $baseEnd = $Text.Length - ($Key.Length - 1) for ( $base = 0 ; $base -lt $baseEnd ; $base++ ){     for ($j = 0 ; $j -lt $Key.Length ; $j++){         if ( $Key[$j]  -ne  $Text[$base + $j] ){ break }     }     if ($j -eq $Key.Length){ break } } if ($base -eq $baseEnd){     '没找到' }else{     "$Key 在 $base" }

把 第一层 for 改成 while

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'ＡＢＡＢ' $base = 0       # edit 1 $baseEnd = $Text.Length - ($Key.Length - 1) while ($base -lt $baseEnd){   # edit 2     for ($j = 0 ; $j -lt $Key.Length ; $j++){         if ( $Key[$j]  -ne  $Text[$base + $j] ){ break }     }     if ($j -eq $Key.Length){ break }     $base += 1       # edit 3 } if ($base -eq $baseEnd){     '没找到' }else{     "$Key 在 $base" }

nwm310

KMP 字串搜寻演算法 - 如何移动？

一开始就比对失败： 　　　比对　　　　　　　　　　移动后 $i　　０１２３４５６７　　　　０１２３４５６７ 　　　ＱＢＡＱＡＢＡＢ　　　　ＱＢＡＱＡＢＡＢ 　　　　Ｘ 　　　　ＡＢＡＢ　　　　　　　　　ＡＢＡＢ $j　　　０１２３　　　　　　　　　０１２３ 　　　$i = 1　　　　　　　　　　$i = 2 　　　$j = 0　　　　　　　　　　$j = 0 　　　一开始就比对失败，此时的 $j 是 ０ 　　　看到 $j 是 ０，就移动１格。 　　　移动１格的方法： $i++  、 $j 不变(仍是０) 比对成功几字之后，然后才比对失败： 　　　比对 $i　　０１２３４５６７ 　　　ＡＢＡＱＡＢＡＢ 　　　｜｜｜Ｘ 　　　ＡＢＡＢ $j　　０１２３ 1.在 $j 索引３比对失败 2.前面３个字是相同的，「相同区」长度为３，内容为ＡＢＡ 3.「相同区」长度 = 比对失败索引值($j) 　　如果在索引１比对失败，那麽「相同区」长度就是１ 　　如果在索引２比对失败，那麽「相同区」长度就是２ 4.在「相同区」里面找移动之后的「次相同区」(上下要相同) 　　　移动前　　　移动后　　　　　错误移法(上下不同) 　　　ＡＢＡ　　　ＡＢＡ　　　　　ＡＢＡ 　　　ＡＢＡ　　　　　ＡＢＡ　　　　ＡＢＡ 　　　「次相同区」长度为１，内容为Ａ 　　　移动格数 = 「相同区」长度 - 「次相同区」长度 　　　 　　　  = ３ - １ 　　　 　　　  = ２ 　　　移动前　　　　　　　　　移动后 $i　　０１２３４５６７　　　　０１２３４５６７ 　　　ＡＢＡＱＡＢＡＢ　　　　ＡＢＡＱＡＢＡＢ 　　　｜｜｜Ｘ　　　　　　　　　　｜ 　　　ＡＢＡＢ　　　　　　　　　　ＡＢＡＢ $j　　０１２３　　　　　　　　　　０１２３ 　　　比对失败位置　　　　　　继续比对位置 　　　$i = 3　　　　　　　　　$i = 3 　　　$j = 3　　　　　　　　　$j = 1 　　　移动２格之后，并且跳过１格不比对 　　　「次相同区」长度，等於「跳过不比对」的长度 　　　原本比对失败的 旧$j 为３ 　　　即将参与比对的 新$j 为１ 　　　新$j = 「次相同区」长度 　　　知道「次相同区」长度，就可得知 新$j 　　　下次比对时，参与比对的 $i 没变(仍和上次一样) 　　　但 $j 变小了，藉此达成「右移」的效果 　　　因为 $i 没有变、不会向后退： 　　　可以不使用 $base + $j 的方式来取得 $i 　　　不再关注「移动几格」 　　　而是关注「次相同区」长度 　　　普通移法的 $i 会向后退： $i　　移动前　　　　　　　　　移动后 　　　０１２３４５６７　　　　０１２３４５６７ 　　　ＡＢＡＢＡＱＡＢＡＢ　　ＡＢＡＱＡＢＡＢ 　　　｜｜｜Ｘ 　　　ＡＢＡＢ　　　　　　　　　ＡＢＡＢ $j　　０１２３　　　　　　　　　０１２３ 　　　$i = 3 比对失败　　　　　从 $i = 1 继续比对。 　　　　　　　　　　　　　　　　$i 改变了、向后退了 5.「相同区」长度为１，「次相同区」长度一定是０ 　　　移动前　　　移动后 　　　Ａ　　　　　Ａ 　　　Ａ　　　　　　Ａ 　　　长度太短，无法去找「次相同区」 　　　 　　　「次相同区」长度为０ 　　　移动格数 = 「相同区」长度 - 「次相同区」长度 　　　 　　　  = １ - ０ 　　　 　　　  = １ 6.别的例子 　　　移动前　　　移动后　　　　　　错误移法(上下不同) 　　　ＡＢＢ　　　ＡＢＢ　　　　　　ＡＢＢ 　　　ＡＢＢ　　　　　　ＡＢＢ　　　　ＡＢＢ 　　　「相同区」长度为３ 　　　「次相同区」长度为０ 　　　移动格数 = 「相同区」长度 - 「次相同区」长度 　　　 　　　  = ３ - ０ 　　　 　　　  = ３ 　　　移动３格之后，即将参与比对的索引值$j 为０ 　　　$j 等於 「次相同区」长度 7.别的例子 　　　移动前　　　　移动后　　　　　　错误移法(上下不同) 　　　ＡＢＡＡ　　　ＡＢＡＡ　　　　　ＡＢＡＡ 　　　ＡＢＡＡ　　　　　　ＡＢＡＡ　　　　ＡＢＡＡ 　　　「相同区」长度为４ 　　　「次相同区」长度为１ 　　　移动格数 = 「相同区」长度 - 「次相同区」长度 　　　 　　　  = ４ - １ 　　　 　　　  = ３ 　　　移动３格之后，可以跳过１格不比对 　　　「次相同区」长度，等於跳过不比对的长度 　　　即将参与比对的索引值$j 为１ 　　　$j 等於 「次相同区」长度 8.别的例子 　　　移动前　　　　移动后　　　　　　错误移法(上下不同) 　　　ＡＢＡＢ　　　ＡＢＡＢ　　　　　ＡＢＡＢ 　　　ＡＢＡＢ　　　　　ＡＢＡＢ　　　　ＡＢＡＢ 　　　「相同区」长度为４ 　　　「次相同区」长度为２ 　　　移动格数 = 「相同区」长度 - 「次相同区」长度 　　　 　　　  = ４ - ２ 　　　 　　　  = ２ 　　　移动２格之后，可以跳过２格不比对 　　　「次相同区」长度，等於跳过不比对的长度 　　　即将参与比对的索引值$j 为２ 　　　$j 等於 「次相同区」长度

   


KMP 字串搜寻演算法 - $base 「移几格」版

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'ＡＢＡＢ' $f = @(0) * $Key.Length <# $f 是一个数组，它的长度和 $Key 一样 索引值 为 比对失败位置(也等於相同区长度) $f[ 比对失败位置 ] 得到 「次相同区」长度 $f[ 旧$j ] 得到 新$j $f[0] = -1  这个值在本程式里不会使用到 $f[1] = 0  相同区长度是 1   次相同区长度一定是 0 此处设定 $f数组 其他元素内容 #> $base = 0 $baseEnd = $Text.Length - ($Key.Length - 1) $j = 0 while ($base -lt $baseEnd){     for ( ; $j -lt $Key.Length ; $j++){ # 这里没有设定 $j 的初始值         if ( $Key[$j]  -ne  $Text[$base + $j] ){ break }     }     if ($j -eq $Key.Length){ break } # 找到了     if ($j -eq 0){$base += 1; continue} # 一开始就比对失败     $base += $j -  $f[$j]      # 移几格？  「相同区」长度 - 「次相同区」长度     $j = $f[$j]    # 设定 新$j 。 「次相同区」长度、用来跳过不比对 } if ($base -eq $baseEnd){     '没找到' }else{     "$Key 在 $base" }

KMP 字串搜寻演算法 - 「$i vs $j」版

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'ＡＢＡＢ' $f = @(0) * $Key.Length <# $f 是一个数组，它的长度和 $Key 一样 $f[旧$j ] 得到 新$j 此处设定 $f 元素内容 #> $i = 0 $j = 0 $ans = -1 while ($i -lt $Text.Length){ # 此处和前例不同     if ($Text[$i] -eq $Key[$j]){ # 比对成功         $i++         $j++         if ($j -eq $Key.Length){ # 找到了             $ans = $i - $j # 注意：要用减法             break         }     }else{         if ($j -ne 0){ # 有「相同区」             $j = $f[$j] # 以「次相同区」长度 设定 新$j。                         # $i 不变                  }else{# 一开始就比对失败。$j是0、不用设定             $i++         }     } } if ($ans -eq -1){ # 此处和前例不同     '没找到' }else{     "$Key 在 $ans" }

nwm310

$f[ ] 的种类

第一种： 　　$f[ 比对失败位置 ] 得到 「下次比对位置」 　　$f[ 相同区长度 ]   得到 「次相同区长度」 　　找到 $Key 之后，此时，$j 等於 $Key.Length 　　要继续找下一个符合的 $Key， 　　不可以用 $f[$j] 得到 新$j  (下次比对位置) 　　因为 $j 超出索引值范围 　　$f[0] = -1 　　本篇教学使用这种 第二种： 　　$f[ 比对失败位置 - 1 ]     得到 「下次比对位置」 　　$f[ 相同区的最后1个索引值 ] 得到   「次相同区长度」 　　找到 $Key 之后，此时，$j 等於 $Key.Length 　　要继续找下一个符合的 $Key，可以用： 　　$f[ $j - 1 ] 得到 新$j  (下次比对位置) 　　$f[0] = 0 第三种： 　　$f[ 比对失败位置 - 1 ]         得到  次相同区的最后1个字的索引值 　　$f[ 相同区的最后1个字的索引值 ] 得到  次相同区的最后1个字的索引值 　　　　　　　　　　　　　　　　　   如果没有次相同区，得到 -1 　　找到 $Key 之后，此时，$j 等於 $Key.Length 　　要继续找下一个符合的 $Key，可以用： 　　$f[ $j - 1 ] 得到 次相同区的最后1个字的索引值 　　$f[0] = -1

如何得知 $f[ ] 是哪一种？

1.确认 $j 的意思     观察「比对时的程式码」     例如：$Text[$i] -eq $Key[$j]         确认 $j 是不是「参与比对的索引值」 2.查看 $f[ ] 的使用情形     如果 $j 是「参与比对的索引值」         第一种：  $j = $f[$j]     第二种：  $j = $f[$j - 1]     第三种：  $j = $f[$j - 1] + 1

在「相同区」里找「次相同区」

$Key = 'ＡＣＡＱＡＣＡＣＱ' 各种长度 的「相同区」 长度　　寻找范围　　　　　移动后　　　　　　次相同区长度 ($len) ６　　　ＡＣＡＱＡＣ　　　ＡＣＡＱＡＣ　　　　　　２ 　　　　ＡＣＡＱＡＣ　　　　　　　ＡＣＡＱＡＣ　　　　　 　　　　　　　　　　　　　确认是否可以沿用长度６的起点 ７　　　ＡＣＡＱＡＣＡ　　ＡＣＡＱＡＣＡ 　　　　ＡＣＡＱＡＣＡ　　　　　　ＡＣＡＱＡＣＡ 长度越长，次相同区的寻找范围就越长 「次相同区」的起点，不需要从「寻找范围」的最左边找起 「长度７」比「长度６」多１字 用多出来的那１字，即「长度７的最后１字」 去比对 $Key[$len] 确认「长度７」的次相同区，是不是「长度６」的次相同区「加长版」 它们「次相同区」起点是不是一样的 如果它们「次相同区」起点是一样的 「长度７的$len」等於「长度６的$len」加１ --- 长度　　寻找范围　　　　　　移动后　　　　　　　次相同区长度 ($len) ７　　　ＡＣＡＱＡＣＡ　　　ＡＣＡＱＡＣＡ　　　　　　３ 　　　　ＡＣＡＱＡＣＡ　　　　　　　ＡＣＡＱＡＣＡ 　　　　　　　　　　　　　　确认是否可以沿用长度７的起点 ８　　　ＡＣＡＱＡＣＡＣ　　ＡＣＡＱＡＣＡＣ 　　　　ＡＣＡＱＡＣＡＣ　　　　　　ＡＣＡＱＡＣＡＣ 「长度８」不可以沿用「长度７」的起点 在长度７的「次相同区」里面移动、寻找「次次相同区」 ＡＣＡ　　　ＡＣＡ ＡＣＡ　　　　　ＡＣＡ 把长度７的「次相同区长度」 ($len 其值为 ３) 当作$f[]的索引值 得到 新$len 即 $len = $f[$len] 新$len = $f[3] = 1 不可以沿用「长度７」的起点 ＡＣＡＱＡＣＡＣ 　　　　ＡＣＡＱＡＣＡＣ 确认是否可以沿用「新起点」　　　以「长度８的最后１字」比对  $Key[$len] ＡＣＡＱＡＣＡＣ 　　　　　　ＡＣＡＱＡＣＡＣ 如果新起点ok： 　　「长度８」的次相同长度，等於 新$len 加 １ 如果新起点不ok： 　　如果新$len不为0，就再一次$len = $f[$len] 　　重复上述动作 　　如果新$len已经是0，就不用再 $len = $f[$len] 　　「长度８」的次相同长度，就是0

nwm310

设定 $f[ ]

# $f[相同区长度] 得到 「次相同区」长度 # $f[旧$j] 得到 新$j # KMP 只有在 $Key长度大於等於 3 才会比普通找法快 if ($Key.Length -lt 3){throw '$Key 长度太小'} #$f 是一个数组，它的长度和 $Key 一样 $f = @(0) * $Key.Length $f[0] = -1 $f[1] = 0 $j = 2 # $j 是相同区长度。它大於等於2，才可以去找「次相同区」 $len = $f[1] # 把 「相同区长度1」的「次相同区长度」，存到 $len while ($j -lt $Key.Length){# $j 是比对失败位置，它小於 $Key.Length     # 现在要从「相同区」里面，找「次相同区」     # 「相同区」里有许多位置，可能是「次相同区」的起点         # $j的「相同区」长度，比 ($j-1) 「相同区」长度多1     # 如果 ($j-1)相同区内的某位置，不能当作「次相同区」起点     # 那麽 $j相同区 也不能使用那个位置，来当作「次相同区」起点         # 於是，我们不从$j「相同区」里的最左边开始找起     # 而是从($j-1)「次相同区」的起点开始找「次相同区」     # $f[$j-1]是 ($j-1)的「次相同区」长度，等於 $len     # $len 是($j-1)「次相同区」长度，不是起点     # ($j-1)的「次相同区」内容为 $Key[0] 到 $Key[$len-1]     # $j相同区 比 ($j-1)相同区多1字     # 用 「$j 相同区的最后1个字」 比对 $Key[$len]     # 来确定此起点是否合适     if ($Key[$j-1] -eq $Key[$len]){ # ($j-1)「次相同区」起点合适         $len++         $f[$j] = $len         $j++     }else{ # ($j-1)「次相同区」起点不合适         if ($len -ne 0){             # ($j-1)的「次相同区长度」不等於0             # 那麽就在($j-1)「次相同区」里面             # 寻找「次次相同区」的「起点」             # 把「次相同区长度」作为 $f[]的索引值             # 取得「次次相同区」长度             # 这里并没有去改变 $j 的值                          # 在while的新一回合             # 会测试  $Key[$j-1] -eq $Key[次次相同区长度]             # 确认「次次相同区」的「起点」是否合适             $len = $f[$len]                  }else{ # $len -eq 0             # 可能1:             # ($j-1)的次相同区长度是0             # $j 相同区 的最后1字 不等於 $Key[0]             #             # 可能2:             # ($j-1)的次相同区长度不是0             # 但「次次相同区」or「次次次相同区」or 「次次次次相同区」是0             # $j 相同区 的最后1字 不等於 $Key[0]             $f[$j] = 0             $j++         }     } }

预先知道：移动后，马上就比对失败

比对　　　　　　　　　　　　移动后 $i　０１２３４５６７８９　　　　　０１２３４５６７８９ 　　ＡＡＣＡＡＱＡＡＣＡＡＣ　　　ＡＡＣＡＡＱＡＡＣＡＡＣ 　　　　　　　Ｘ　　　　　　　　　　　　　　Ｘ 　　ＡＡＣＡＡＣ　　　　　　　　　　　　ＡＡＣＡＡＣ $j　０１２３４５　　　　　　　　　　　　０１２３４５ 　　比对失败位置： $j = ５ 　　「相同区」：ＡＡＣＡＡ 　　「次相同区」：ＡＡ 　　「次相同区」长度：２ 　　如果「次相同区」后面的字，和比对失败位置的字相同 　　即，如果 $Key[2] 等於 $Key[5] 　　移动后的第一次比对，马上就比对失败

设定 $f[ ] 改良版

if ($Key.Length -lt 3){throw '$Key 长度太小'} #$f 是一个数组，它的长度和 $Key 一样 $f = @(0) * $Key.Length $f[0] = -1 $f[1] = 0 $j = 2 $len = $f[1] while ($j -lt $Key.Length){     if ($Key[$j-1] -eq $Key[$len]){         $len++         if ($Key[$j] -ne $Key[$len]){ # ok             $f[$j] = $len         }else{ # 移动后，马上就比对失败                 #在制表时，就先设定到最适合的次相同区长度                 #避免正式比对时，多做额外的比对             $f[$j] = $f[$len]         }         $j++     }else{         if ($len -ne 0){             $len = $f[$len]         }else{ # $len -eq 0             $f[$j] = 0             $j++         }     } }

nwm310

KMP 字串搜寻演算法 - 最终版

$Text = 'ＡＢＡＱＡＢＡＢ' $Key = 'ＡＢＡＢ' #======= 设定 $f[] ======== if ($Key.Length -lt 3){throw '$Key 长度太小'} #$f 是一个数组，它的长度和 $Key 一样 $f = @(0) * $Key.Length $f[0] = -1 $f[1] = 0 $j = 2 $len = $f[1] while ($j -lt $Key.Length){     if ($Key[$j-1] -eq $Key[$len]){         $len++         if ($Key[$j] -ne $Key[$len]){             $f[$j] = $len         }else{             $f[$j] = $f[$len]         }         $j++     }else{         if ($len -ne 0){             $len = $f[$len]         }else{ # $len -eq 0             $f[$j] = 0             $j++         }     } } #======= 开始寻找 ======== $i = 0 $j = 0 $ans = -1 while ($i -lt $Text.Length){     if ($Text[$i] -eq $Key[$j]){         $i++         $j++         if ($j -eq $Key.Length){             $ans = $i - $j             break         }     }else{         if ($j -ne 0){             $j = $f[$j]                  }else{             $i++         }     } } if ($ans -eq -1){     '没找到' }else{     "$Key 在 $ans" }

whiter

字符串有indexOf方法查找索引, 可以简化代码, 省掉循环