批处理之家 - Powered by Discuz! Board

标题: [原创教程] KMP 字串搜寻演算法 [打印本页]

作者: nwm310 时间: 2020-10-11 11:08 标题: KMP 字串搜寻演算法

本帖最后由 nwm310 于 2020-10-11 11:11 编辑

注意事项：
-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 时间: 2020-10-11 11:12

本帖最后由 nwm310 于 2020-10-11 12:26 编辑

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 时间: 2020-10-11 12:06

$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 时间: 2020-10-11 12:12

设定 $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 时间: 2020-10-11 12:17

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 时间: 2021-9-4 21:41

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

欢迎光临批处理之家 (http://bbs.bathome.net/)