注意事項：
-eq 不區分大小寫。如果有需要，請改用 -ceqPS 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" }
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" }
$f[ ] 的種類
第一種： $f[ 比對失敗位置 ] 得到 「下次比對位置」 $f[ 相同區長度 ] 得到 「次相同區長度」 找到 $Key 之後，此時，$j 等於 $Key.Length 要繼續找下一個符合的 $Key， 不可以用 $f[$j] 得到 新$j (下次比對位置) 因為 $j 超出索引值範圍 $f[0] = -1 本篇教學使用這種 相關網站： Knuth-Morris-Pratt algorithm [TIL] 有關字串搜尋的演算法: KMP - kkdai.github.io
第二種： $f[ 比對失敗位置 - 1 ] 得到 「下次比對位置」 $f[ 相同區的最後1個索引值 ] 得到 「次相同區長度」 找到 $Key 之後，此時，$j 等於 $Key.Length 要繼續找下一個符合的 $Key，可以用： $f[ $j - 1 ] 得到 新$j (下次比對位置) $f[0] = 0 相關網站： GeeksforGeeks KMP C++ source code 字符串匹配的KMP算法 - 阮一峰的网络日志 KMP算法詳解. 詳細介紹KMP(Knuth-Morris-Pratt)字串尋找算法 | by CHEN TSU PEI | NLP-trend-and-review | Medium [分享] KMP(Knuth–Morris–Pratt algorithm) - 看板 b99902HW - 批踢踢實業坊
第三種： $f[ 比對失敗位置 - 1 ] 得到 次相同區的最後1個字的索引值 $f[ 相同區的最後1個字的索引值 ] 得到 次相同區的最後1個字的索引值 如果沒有次相同區，得到 -1 找到 $Key 之後，此時，$j 等於 $Key.Length 要繼續找下一個符合的 $Key，可以用： $f[ $j - 1 ] 得到 次相同區的最後1個字的索引值 $f[0] = -1 相關網站： KMP 字串比對演算法 | Mr. Opengate 演算法筆記 - String Searching 資結筆記 - KMP演算法 - j2492104的創作 - 巴哈姆特 [理工] [演算法]-KMP algorithm - 看板 Grad-ProbAsk - 批踢踢實業坊
如何得知 $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
設定 $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++ } } }
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" }
沒有留言:
張貼留言