批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程
[批处理文件精品]批处理版照片整理器[批处理文件精品]纯批处理备份&还原驱动在线第三方下载
返回列表 发帖

[原创教程] 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 = 'ABAQABAB'
$Key = 'B'

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 = 'ABAQABAB'
$Key = 'ABAB'

$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 = 'ABAQABAB'
$Key = 'ABAB'

$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"
}
1

评分人数

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

KMP 字串搜寻演算法 - 如何移动?
一开始就比对失败:
   比对          移动后
$i  01234567    01234567
   QAQABAB    QBQABAB
    X
    ABAB         ABAB
$j   0123         0123

   $i = 1          $i = 2
   $j = 0          $j = 0

   一开始就比对失败,此时的 $j 是 0
   看到 $j 是 0,就移动1格。

   移动1格的方法: $i++  、 $j 不变(仍是0)

比对成功几字之后,然后才比对失败:

   比对
$i  01234567
   ABAABAB
   |||X
   ABAB
$j  0123


1.$j 索引3比对失败
2.前面3个字是相同的,「相同区」长度为3,内容为ABA
3.「相同区」长度 = 比对失败索引值($j)

  如果在索引1比对失败,那麽「相同区」长度就是1
  如果在索引2比对失败,那麽「相同区」长度就是2

4.在「相同区」里面找移动之后的「次相同区」(上下要相同)
   移动前   移动后     错误移法(上下不同)
   ABA   ABA     ABA
   ABA     ABA    ABA

   「次相同区」长度为1,内容为A
   移动格数 = 「相同区」长度 - 「次相同区」长度
         =-
         =

   移动前         移动后
$i  01234567    01234567
   ABAABAB    ABAABAB
   |||X          |
   ABAB          ABAB
$j  0123          0123

   比对失败位置      继续比对位置
   $i = 3         $i = 3
   $j = 3         $j = 1

   移动2格之后,并且跳过1格不比对
   「次相同区」长度,等於「跳过不比对」的长度

   原本比对失败的 旧$j 为3
   即将参与比对的 新$j 为1
   新$j = 「次相同区」长度
   知道「次相同区」长度,就可得知 新$j

   下次比对时,参与比对的 $i 没变(仍和上次一样)
   $j 变小了,藉此达成「右移」的效果

   因为 $i 没有变、不会向后退:
   可以不使用 $base + $j 的方式来取得 $i
   不再关注「移动几格」
   而是关注「次相同区」长度

   普通移法的 $i 会向后退:
$i  移动前         移动后
   01234567    01234567
   ABAAQABAB  AAQABAB
   |||X
   ABAB         ABAB
$j  0123         0123

   $i = 3 比对失败     从 $i = 1 继续比对。
                $i 改变了、向后退了

5.「相同区」长度为1,「次相同区」长度一定是0
   移动前   移动后
   A     A
   A      A

   长度太短,无法去找「次相同区」
   
   「次相同区」长度为0
   移动格数 = 「相同区」长度 - 「次相同区」长度
         =-
         =

6.别的例子
   移动前   移动后      错误移法(上下不同)
   ABB   ABB      ABB
   ABB      ABB    ABB

   「相同区」长度为3
   「次相同区」长度为0
   移动格数 = 「相同区」长度 - 「次相同区」长度
         =-
         =

   移动3格之后,即将参与比对的索引值$j 为0
   $j 等於 「次相同区」长度

7.别的例子
   移动前    移动后      错误移法(上下不同)
   ABAA   ABAA     ABAA
   ABAA      ABAA    ABAA

   「相同区」长度为4
   「次相同区」长度为1
   移动格数 = 「相同区」长度 - 「次相同区」长度
         =-
         =

   移动3格之后,可以跳过1格不比对
   「次相同区」长度,等於跳过不比对的长度
   即将参与比对的索引值$j 为1
   $j 等於 「次相同区」长度

8.别的例子
   移动前    移动后      错误移法(上下不同)
   ABAB   ABAB     ABAB
   ABAB     ABAB    ABAB

   「相同区」长度为4
   「次相同区」长度为2
   移动格数 = 「相同区」长度 - 「次相同区」长度
         =-
         =

   移动2格之后,可以跳过2格不比对
   「次相同区」长度,等於跳过不比对的长度
   即将参与比对的索引值$j 为2
   $j 等於 「次相同区」长度

   


KMP 字串搜寻演算法 - $base 「移几格」版
$Text = 'ABAQABAB'
$Key = 'ABAB'

$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 = 'ABAQABAB'
$Key = 'ABAB'

$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"
}

TOP

$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 = 'ACAQACACQ'

各种长度 的「相同区」

长度  寻找范围     移动后      次相同区长度 ($len)
6   ACAQAC   ACAQAC      
    ACAQAC       ACAQAC     

             确认是否可以沿用长度6的起点
7   ACAQACA  ACAQAC
    ACAQACA      ACQACA

长度越长,次相同区的寻找范围就越长
「次相同区」的起点,不需要从「寻找范围」的最左边找起

「长度7」比「长度6」多1字
用多出来的那1字,即「长度7的最后1字」
去比对 $Key[$len]
确认「长度7」的次相同区,是不是「长度6」的次相同区「加长版」
它们「次相同区」起点是不是一样的
如果它们「次相同区」起点是一样的
「长度7的$len」等於「长度6的$len」加

---

长度  寻找范围      移动后       次相同区长度 ($len)
7   ACAQACA   ACAQACA      
    ACAQACA       ACAQACA

              确认是否可以沿用长度7的起点
8   ACAQACAC  ACAQACA
    ACAQACAC      ACAACAC

「长度8」不可以沿用「长度7」的起点

在长度7的「次相同区」里面移动、寻找「次次相同区」
ACA   AC
ACA     CA

把长度7的「次相同区长度」 ($len 其值为 3)
当作$f[]的索引值
得到 新$len
$len = $f[$len]
$len = $f[3] = 1


不可以沿用「长度7」的起点
ACAQACA
    ACAACAC

确认是否可以沿用「新起点」   以「长度8的最后1字」比对  $Key[$len]
ACAQAC
      AQACAC



如果新起点ok:
  「长度8」的次相同长度,等於 新$len 加 1

如果新起点不ok:
  如果新$len不为0,就再一次$len = $f[$len]
  重复上述动作

  如果新$len已经是0,就不用再 $len = $f[$len]
  「长度8」的次相同长度,就是0

TOP

设定 $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 0123456789     0123456789
  AACAAAACAAC   AACAAAACAAC
       X              X
  AAAA            AAAA
$j 012345            012345

  比对失败位置: $j =
  「相同区」:AACAA
  「次相同区」:AA
  「次相同区」长度:2

  如果「次相同区」后面的字,和比对失败位置的字相同
  即,如果 $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++
        }
    }
}

TOP

KMP 字串搜寻演算法 - 最终版
$Text = 'ABAQABAB'
$Key = 'ABAB'

#======= 设定 $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"
}

TOP

返回列表