注意事項：
-eq 不區分大小寫。如果有需要，請改用
-ceq
PS C:\> 'a' -eq 'A'
True
PS C:\> 'a' -ceq 'A'
False
在 $Text 裡面找 $Key ( 1個字 )
$Text = 'ＱＱＱＱＱＢＣＡＢＣ' # 10字
$Key = 'Ｂ'
for ( $base = 0 ; $base -lt 10 ; $base++ ){ # 10 是 $Text的長度
if ( $Key -eq $Text[$base] ){ break }
}
if ($base -eq 10){ # 10 是 $Text的長度
'沒找到'
}else{
"$Key 在 $base"
}
在 $Text 裡面找 $Key ( 2個字 or 2個字以上)
$Text = 'ＱＱＱＱＱＢＣＡＢＣ' # 10字
$Key = 'ＢＣＡＢＣ' # 5字
for ( $base = 0 ; $base -lt 6 ; $base++ ){ # $Text長度 - ($Key長度 - 1 )
# 10 - ( 5 - 1 ) = 6
for ($i = 0 ; $i -lt 5 ; $i++){ # 5 是 $Key的長度
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq 5){ break }
}
if ($base -eq 6){
'沒找到'
}else{
"$Key 在 $base"
}
前例的另一種寫法：第二層 for 改成「後往前」找
$Text = 'ＱＱＱＱＱＢＣＡＢＣ'
$Key = 'ＢＣＡＢＣ'
for ( $base = 0 ; $base -lt 6 ; $base++ ){
for ($i = 4 ; $i -ge 0 ; $i--){ # $i 4 到 0
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq -1 ){ break } # $i -eq -1
}
if ($base -eq 6){
'沒找到'
}else{
"$Key 在 $base"
}
把 第一層 for 改成 while
$Text = 'ＱＱＱＱＱＢＣＡＢＣ'
$Key = 'ＢＣＡＢＣ'
$base = 0 # $base = 0
while ($base -lt 6){ # $base -lt 6
for ($i = 4 ; $i -ge 0 ; $i--){
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq -1 ){ break }
$base += 1 # $base += 1
}
if ($base -eq 6){
'沒找到'
}else{
"$Key 在 $base"
}
Boyer-Moore字串搜尋演算法
$Text = 'ＱＱＱＱＱＢＣＡＢＣ'
$Key = 'ＢＣＡＢＣ'
<#
1.
「$base 移動方向」必須和「$i 比對方向」相反
根據「$base 移動方向」，來決定「$i 比對方向」
當 $base 移動方向 → 則 $i 比對方向 ←
2.
根據「$i 比對方向」和「$Key」來製表 $Bc 和 $Gs
3.
比對失敗時，使用 $Bc $Gs 兩者之間的最大值，來改變 $base
#>
$Bc = $Gs = $null
<# 步驟 2
此處設定 $Bc 和 $Gs
#>
$base = 0
while ($base -lt 6){
#步驟 1 方向相反
for ($i = 4 ; $i -ge 0 ; $i--){
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq -1 ){ break }
#步驟 3 移動幾格
[int]$badChar = $Text[$base + $i]
if ( $Bc[$i][ $badChar ] -gt $Gs[$i] ){
$base += $Bc[$i][ $badChar ]
}else{
$base += $Gs[$i]
}
}
if ($base -ge 6){
'沒找到'
}else{
"$Key 在 $base"
}
BM：從前面往後找
$Text = 'ＱＱＱＱＱＢＣＡＢＣ'
$Key = 'ＢＣＡＢＣ'
if ($Key.length -lt 2 -or $Text.Length -lt $Key.Length ){'bye';pause;exit}
#===== 製表 $Bc =====
$Bc = @( $Key.Length ) * 64KB
for ( $i = 0 ; $i -le $Key.Length - 2 ; $i++ ){
[int]$badChar = $Key[$i]
$Bc[ $badChar ] = $Key.Length - 1 - $i
}
#===== 製表 $Gs =====
$Gs = @( $Key.Length ) * $Key.Length
$good = $Key.Length - 1
$defaultMove = $Key.Length
for($test = 0; $test -le $Key.Length - 2; $test++){
$g = $good
$t = $test
for ( ; $t -ge 0 ; $g--,$t--){
if ($Key[$g] -ne $Key[$t]) {break}
}
if ($t -eq $test){
$Gs[$good - $test -1 ] = $defaultMove
}elseif($t -eq -1){
$Gs[$g] = $good - $test
$defaultMove = $good - $test
}else{
$Gs[$g] = $good - $test
}
}
$Gs[$Key.Length - 1] = 1
#==============
# 如果$Key是固定的，可以事先算好，把$Bc $Gs內容直接寫在 ps1
# 就可以不用臨時製表了
# $BcStr = "$Bc" -replace ' ', ','
# $GsStr = "$Gs" -replace ' ', ','
#===== 開始尋找 =====
$base = 0
while ($base -lt $Text.length - $Key.Length + 1){
# 方向相反
for ($i = $Key.Length - 1 ; $i -ge 0 ; $i--){
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq -1 ){ break }
# 移動幾格
[int]$badChar = $Text[$base + $i]
$B_move = $Bc[ $badChar ] - ($Key.Length - 1 - $i)
#有時 $B_move 值 會是負的。這時需要靠 $Gs[$i]
if ( $B_move -gt $Gs[$i] ){
$base += $B_move
}else{
$base += $Gs[$i]
}
}
#===== 結果 =====
if ($base -ge $Text.length - $Key.Length + 1){
"$Key not found"
}else{
"$Key in $base"
}
pause
BM：從後面往前找
$Text = 'ＢＣＡＢＣＱＱＱＱＱ'
$Key = 'ＢＣＡＢＣ'
if ($Key.length -lt 2 -or $Text.Length -lt $Key.Length ){'bye';pause;exit}
#===== 製表 $Bc =====
$Bc = @( $Key.Length ) * 64KB
for ( $i = $Key.Length - 1 ; $i -ge 1 ; $i-- ){
[int]$badChar = $Key[$i]
$Bc[ $badChar ] = $i - 0
}
#===== 製表 $Gs =====
$Gs = @( $Key.Length ) * $Key.Length
$good = 0
$defaultMove = $Key.Length
for($test = $Key.Length - 1; $test -ge 1; $test--){
$g = $good
$t = $test
for ( ; $t -le $Key.Length - 1 ; $g++,$t++){
if ($Key[$g] -ne $Key[$t]) {break}
}
if ($t -eq $test){
$Gs[$Key.Length - $t ] = $defaultMove
}elseif($t -eq $Key.Length){
$Gs[$g] = $test - $good
$defaultMove = $test - $good
}else{
$Gs[$g] = $test - $good
}
}
$Gs[0] = 1
#==============
# 如果$Key是固定的，可以事先算好，把$Bc $Gs內容直接寫在 ps1
# 就可以不用臨時製表了
# $BcStr = "$Bc" -replace ' ', ','
# $GsStr = "$Gs" -replace ' ', ','
#===== 開始尋找 =====
$base = $Text.length - 1 - ($Key.Length - 1)
while ($base -ge 0){
# 方向相反
for ($i = 0 ; $i -le $Key.Length - 1 ; $i++){
if ( $Key[$i] -ne $Text[$base + $i] ){ break }
}
if ($i -eq $Key.Length ){ break }
# 移動幾格
[int]$badChar = $Text[$base + $i]
$B_move = $Bc[ $badChar ] - $i
#有時 $B_move 值 會是負的。這時需要靠 $Gs[$i]
if ( $B_move -gt $Gs[$i] ){
$base -= $B_move
}else{
$base -= $Gs[$i]
}
}
#===== 結果 =====
if ($base -lt 0){
"$Key not found"
}else{
"$Key in $base"
}
pause
相關文章：
參考資料：
沒有留言:
張貼留言