批处理之家's Archiver

nwm310 发表于 2020-10-11 11:08

KMP 字串搜寻演算法

[i=s] 本帖最后由 nwm310 于 2020-10-11 11:11 编辑 [/i]

注意事项:
[b]-eq[/b] 不区分大小写。如果有需要,请改用 [b]-ceq[/b]
[table=98%,#012456]
[tr][td][font=monospace][size=12px][color=#dddddd]PS C:\> 'a'  -eq  'A'
True
PS C:\> 'a'  -ceq  'A'
False
[/color][/size][/font][/td][/tr]
[/table]

在 $Text 里面找 $Key ( 1个字 )
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'B'[/color]

[color=#c586c0]for[/color] ( [color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color] ; [color=#9cdcfe]$base[/color][color=#d4d4d4]++[/color] ){
    [color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color]] ){ [color=#c586c0]break[/color] }
}

[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Text.Length[/color]){
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]

在 $Text 里面找 $Key ( 2个字 or 2个字以上)
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]

[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#c586c0]for[/color] ( [color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color] ; [color=#9cdcfe]$base[/color][color=#d4d4d4]++[/color] ){

    [color=#c586c0]for[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){
        [color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]  [color=#d4d4d4]-ne[/color]  [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
    }

    [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] }
}

[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]


把 第一层 for 改成 while
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]

[color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]       [color=#7ca668]# edit 1[/color]
[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#c586c0]while[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color]){   [color=#7ca668]# edit 2[/color]

    [color=#c586c0]for[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color] ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){
        [color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]  [color=#d4d4d4]-ne[/color]  [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
    }

    [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] }
    [color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#b5cea8]1[/color]       [color=#7ca668]# edit 3[/color]
}

[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]

nwm310 发表于 2020-10-11 11:12

[i=s] 本帖最后由 nwm310 于 2020-10-11 12:26 编辑 [/i]

KMP 字串搜寻演算法 - 如何移动?
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][b][color=cyan]一开始就比对失败:[/color][/b]
   比对          移动后
[color=#9cdcfe]$i[/color]  01234567    01234567
   Q[b][color=#ff00ff]B[/color][/b]AQABAB    QB[b][color=#ff00ff]A[/color][/b]QABAB
    X
    ABAB         ABAB
[color=#9cdcfe]$j[/color]   0123         0123

   [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color]          [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
   [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]          [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]

   一开始就比对失败,此时的 [color=#9cdcfe]$j[/color] 是 0
   看到 [color=#9cdcfe]$j[/color] 是 0,就移动1格。

   移动1格的方法: [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]  、 [color=#9cdcfe]$j[/color] 不变(仍是0)

[b][color=cyan]比对成功几字之后,然后才比对失败:[/color][/b]

   比对
[color=#9cdcfe]$i[/color]  01234567
   ABA[b][color=#ff00ff]Q[/color][/b]ABAB
   |||X
   ABAB
[color=#9cdcfe]$j[/color]  0123


[color=#b5cea8]1.[/color]在 [color=#9cdcfe]$j[/color] 索引3比对失败
[color=#b5cea8]2.[/color]前面3个字是相同的,「相同区」长度为3,内容为ABA
[color=#b5cea8]3[/color].「相同区」长度 [color=#d4d4d4]=[/color] 比对失败索引值([color=#9cdcfe]$j[/color])

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

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

   「次相同区」长度为1,内容为A
   移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
         [color=#d4d4d4]=[/color] 3 [color=#d4d4d4]-[/color] 1
         [color=#d4d4d4]=[/color] 2

   移动前         移动后
[color=#9cdcfe]$i[/color]  01234567    01234567
   ABA[b][color=#ff00ff]Q[/color][/b]ABAB    ABA[b][color=#ff00ff]Q[/color][/b]ABAB
   |||X          |
   ABAB          ABAB
[color=#9cdcfe]$j[/color]  0123          0123

   比对失败位置      继续比对位置
   [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color]         [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color]
   [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color]         [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color]

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

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

   [b][color=cyan]下次比对时,参与比对的 [color=#9cdcfe]$i[/color] 没变(仍和上次一样)[/color][/b]
   [b][color=cyan]但 [color=#9cdcfe]$j[/color] 变小了,藉此达成「右移」的效果[/color][/b]

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

   普通移法的 [color=#9cdcfe]$i[/color] 会向后退:
[color=#9cdcfe]$i[/color]  移动前         移动后
   01234567    01234567
   ABA[b][color=#ff00ff]B[/color][/b]AQABAB  A[b][color=#ff00ff]B[/color][/b]AQABAB
   |||X
   ABAB         ABAB
[color=#9cdcfe]$j[/color]  0123         0123

   [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]3[/color] 比对失败     从 [color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]1[/color] 继续比对。
                [color=#9cdcfe]$i[/color] 改变了、向后退了

[color=#b5cea8]5[/color].「相同区」长度为1,「次相同区」长度一定是0
   移动前   移动后
   A     A
   A      A

   长度太短,无法去找「次相同区」
   
   「次相同区」长度为0
   移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
         [color=#d4d4d4]=[/color] 1 [color=#d4d4d4]-[/color] 0
         [color=#d4d4d4]=[/color] 1

[color=#b5cea8]6.[/color]别的例子
   移动前   移动后      错误移法(上下不同)
   ABB   ABB      ABB
   ABB      ABB    ABB

   「相同区」长度为3
   「次相同区」长度为0
   移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
         [color=#d4d4d4]=[/color] 3 [color=#d4d4d4]-[/color] 0
         [color=#d4d4d4]=[/color] 3

   移动3格之后,即将参与比对的索引值[color=#9cdcfe]$j[/color] 为0
   [color=#9cdcfe]$j[/color] 等於 「次相同区」长度

[color=#b5cea8]7.[/color]别的例子
   移动前    移动后      错误移法(上下不同)
   ABAA   ABAA     ABAA
   ABAA      ABAA    ABAA

   「相同区」长度为4
   「次相同区」长度为1
   移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
         [color=#d4d4d4]=[/color] 4 [color=#d4d4d4]-[/color] 1
         [color=#d4d4d4]=[/color] 3

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

[color=#b5cea8]8.[/color]别的例子
   移动前    移动后      错误移法(上下不同)
   ABAB   ABAB     ABAB
   ABAB     ABAB    ABAB

   「相同区」长度为4
   「次相同区」长度为2
   移动格数 [color=#d4d4d4]=[/color] 「相同区」长度 [color=#d4d4d4]-[/color] 「次相同区」长度
         [color=#d4d4d4]=[/color] 4 [color=#d4d4d4]-[/color] 2
         [color=#d4d4d4]=[/color] 2

   移动2格之后,可以跳过2格不比对
   「次相同区」长度,等於跳过不比对的长度
   即将参与比对的索引值[color=#9cdcfe]$j[/color] 为2
   [color=#9cdcfe]$j[/color] 等於 「次相同区」长度
[/color][/size][/font][/td][/tr]
[/table]
   


KMP 字串搜寻演算法 - $base 「移几格」版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]

[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#7ca668]<#[/color]
[color=#7ca668] $f 是一个数组,它的长度和 $Key 一样[/color]
[color=#7ca668] 索引值 为 比对失败位置(也等於相同区长度)[/color]
[color=#7ca668] $f[ 比对失败位置 ] 得到 「次相同区」长度[/color]
[color=#7ca668] $f[ 旧$j ] 得到 新$j[/color]
[color=#7ca668] $f[0] = -1  这个值在本程式里不会使用到[/color]
[color=#7ca668] $f[1] = 0  相同区长度是 1   次相同区长度一定是 0[/color]

[color=#7ca668] 此处设定 $f数组 其他元素内容[/color]
[color=#7ca668]#>[/color]

[color=#9cdcfe]$base[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$baseEnd[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$Text.Length[/color] [color=#d4d4d4]-[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color])
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$baseEnd[/color]){

    [color=#c586c0]for[/color] ( ; [color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color] ; [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]){ [color=#7ca668]# 这里没有设定 $j 的初始值[/color]
        [color=#c586c0]if[/color] ( [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]  [color=#d4d4d4]-ne[/color]  [color=#9cdcfe]$Text[/color][[color=#9cdcfe]$base[/color] [color=#d4d4d4]+[/color] [color=#9cdcfe]$j[/color]] ){ [color=#c586c0]break[/color] }
    }

    [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#c586c0]break[/color] } [color=#7ca668]# 找到了[/color]
    [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]0[/color]){[color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#b5cea8]1[/color]; [color=#c586c0]continue[/color]} [color=#7ca668]# 一开始就比对失败[/color]
    [color=#9cdcfe]$base[/color] [color=#d4d4d4]+=[/color] [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color]  [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]      [color=#7ca668]# 移几格?  「相同区」长度 - 「次相同区」长度[/color]
    [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]    [color=#7ca668]# 设定 新$j 。 「次相同区」长度、用来跳过不比对[/color]

}

[color=#c586c0]if[/color] ([color=#9cdcfe]$base[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$baseEnd[/color]){
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$base[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]



KMP 字串搜寻演算法 - 「$i vs $j」版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]

[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]
[color=#7ca668]<#[/color]
[color=#7ca668] $f 是一个数组,它的长度和 $Key 一样[/color]
[color=#7ca668] $f[旧$j ] 得到 新$j[/color]
[color=#7ca668] 此处设定 $f 元素内容[/color]
[color=#7ca668]#>[/color]

[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$i[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color]){ [color=#7ca668]# 此处和前例不同[/color]
    [color=#c586c0]if[/color] ([color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]){ [color=#7ca668]# 比对成功[/color]
        [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
        [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]

        [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){ [color=#7ca668]# 找到了[/color]
            [color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]-[/color] [color=#9cdcfe]$j[/color] [color=#7ca668]# 注意:要用减法[/color]
            [color=#c586c0]break[/color]
        }
    }[color=#c586c0]else[/color]{
        [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){ [color=#7ca668]# 有「相同区」[/color]
            [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#7ca668]# 以「次相同区」长度 设定 新$j。[/color]
                        [color=#7ca668]# $i 不变[/color]
        
        }[color=#c586c0]else[/color]{[color=#7ca668]# 一开始就比对失败。$j是0、不用设定[/color]
            [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
        }
    }
}

[color=#c586c0]if[/color] ([color=#9cdcfe]$ans[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]-1[/color]){ [color=#7ca668]# 此处和前例不同[/color]
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$ans[/color][color=#ce9178]"[/color]
}
[/color][/size][/font][/td][/tr]
[/table]

nwm310 发表于 2020-10-11 12:06

$f[ ] 的种类
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][b][color=cyan]第一种:[/color][/b]
  [color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] ] 得到 「下次比对位置」
  [color=#9cdcfe]$f[/color][ [color=#569cd6]相同区长度[/color] ]   得到 「次相同区长度」

  找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
  要继续找下一个符合的 [color=#9cdcfe]$Key[/color],
  不可以用 [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] 得到 新[color=#9cdcfe]$j[/color]  (下次比对位置)
  因为 [color=#9cdcfe]$j[/color] 超出索引值范围

  [color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]

  本篇教学使用这种


[b][color=cyan]第二种:[/color][/b]
  [color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ]     得到 「下次比对位置」
  [color=#9cdcfe]$f[/color][ [color=#569cd6]相同区的最后1个索引值[/color] ] 得到   「次相同区长度」

  找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
  要继续找下一个符合的 [color=#9cdcfe]$Key[/color],可以用:
  [color=#9cdcfe]$f[/color][ [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 新[color=#9cdcfe]$j[/color]  (下次比对位置)

  [color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]


[b][color=cyan]第三种:[/color][/b]
  [color=#9cdcfe]$f[/color][ [color=#569cd6]比对失败位置[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ]         得到  次相同区的最后1个字的索引值
  [color=#9cdcfe]$f[/color][ [color=#569cd6]相同区的最后1个字的索引值[/color] ] 得到  次相同区的最后1个字的索引值
                    如果没有次相同区,得到 [color=#b5cea8]-1[/color]

  找到 [color=#9cdcfe]$Key[/color] 之后,此时,[color=#9cdcfe]$j[/color] 等於 [color=#9cdcfe]$Key.Length[/color]
  要继续找下一个符合的 [color=#9cdcfe]$Key[/color],可以用:
  [color=#9cdcfe]$f[/color][ [color=#9cdcfe]$j[/color] [color=#d4d4d4]-[/color] [color=#b5cea8]1[/color] ] 得到 次相同区的最后1个字的索引值

  [color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]

[/color][/size][/font][/td][/tr]
[/table]


如何得知 $f[ ] 是哪一种?
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd]1.确认 [color=#9cdcfe]$j[/color] 的意思
    观察「比对时的程式码」
    例如:[color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] -eq [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]
   
    确认 [color=#9cdcfe]$j[/color] 是不是「参与比对的索引值」

2.查看 [color=#9cdcfe]$f[/color][ ] 的使用情形
    如果 [color=#9cdcfe]$j[/color] 是「参与比对的索引值」
   
    第一种:  [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]
    第二种:  [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color] - 1]
    第三种:  [color=#9cdcfe]$j[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color] - 1] + 1
[/color][/size][/font][/td][/tr]
[/table]


在「相同区」里找「次相同区」
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Key[/color] = [color=#ce9178]'ACAQACACQ'[/color]

各种长度 的「相同区」

长度  寻找范围     移动后      次相同区长度 ([b][color=cyan]$len[/color][/b])
6   A[b][color=cyan]CAQAC[/color][/b]   ACAQ[b][color=cyan]AC[/color][/b]      [b][color=cyan]2[/color][/b]
    ACAQAC       [b][color=cyan]AC[/color][/b]AQAC     

             确认是否可以沿用长度6的起点
7   A[b][color=cyan]CAQACA[/color][/b]  ACAQ[b][color=cyan]AC[/color][/b][b][color=#ff00ff]A[/color][/b]
    ACAQACA      [b][color=cyan]AC[/color][/b][color=#ff00ff]A[/color][/b]QACA

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

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

---

长度  寻找范围      移动后       次相同区长度 ([b][color=cyan]$len[/color][/b])
7   A[b][color=cyan]CAQACA[/color][/b]   ACAQ[b][color=cyan]ACA[/color][/b]      [b][color=cyan]3[/color][/b]
    ACAQACA       [b][color=cyan]ACA[/color][/b]QACA

              确认是否可以沿用长度7的起点
8   A[b][color=cyan]CAQACAC[/color][/b]  ACAQ[b][color=cyan]ACA[/color][/b][b][color=red]C[/color][/b]
    ACAQACAC      [b][color=cyan]ACA[/color][/b][b][color=red]Q[/color][/b]ACAC

「长度8」[b][color=cyan]不可以[/color][/b]沿用「长度7」的起点

[b][color=cyan]在长度7的「次相同区」里面移动、寻找「次次相同区」[/color][/b]
ACA   AC[b][color=cyan]A[/color][/b]
ACA     [b][color=cyan]A[/color][/b]CA

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


[b][color=cyan]不可以[/color][/b]沿用「长度7」的起点
ACAQ[b][color=cyan]ACA[/color][/b][b][color=red]C[/color][/b]
    [b][color=cyan]ACA[/color][/b][b][color=red]Q[/color][/b]ACAC

确认是否可以沿用「新起点」   以「长度8的最后1字」比对  [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]
ACAQAC[b][color=cyan]A[/color][/b][b][color=#ff00ff]C[/color][/b]
      [b][color=cyan]A[/color][/b][b][color=#ff00ff]C[/color][/b]AQACAC



如果新起点ok:
  「长度8」的次相同长度,等於 新[color=#9cdcfe]$len[/color] 加 1

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

  如果新$len已经是0,就不用再 [color=#9cdcfe]$len[/color] = [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
  「长度8」的次相同长度,就是0
[/color][/size][/font][/td][/tr]
[/table]

nwm310 发表于 2020-10-11 12:12

设定 $f[ ]
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#7ca668]# $f[相同区长度] 得到 「次相同区」长度[/color]
[color=#7ca668]# $f[旧$j] 得到 新$j[/color]

[color=#7ca668]# KMP 只有在 $Key长度大於等於 3 才会比普通找法快[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}

[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]

[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]

[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color] [color=#7ca668]# $j 是相同区长度。它大於等於2,才可以去找「次相同区」[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#7ca668]# 把 「相同区长度1」的「次相同区长度」,存到 $len[/color]

[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){[color=#7ca668]# $j 是比对失败位置,它小於 $Key.Length[/color]

    [color=#7ca668]# 现在要从「相同区」里面,找「次相同区」[/color]
    [color=#7ca668]# 「相同区」里有许多位置,可能是「次相同区」的起点[/color]
   
    [color=#7ca668]# $j的「相同区」长度,比 ($j-1) 「相同区」长度多1[/color]
    [color=#7ca668]# 如果 ($j-1)相同区内的某位置,不能当作「次相同区」起点[/color]
    [color=#7ca668]# 那麽 $j相同区 也不能使用那个位置,来当作「次相同区」起点[/color]
   
    [color=#7ca668]# 於是,我们不从$j「相同区」里的最左边开始找起[/color]
    [color=#7ca668]# 而是从($j-1)「次相同区」的起点开始找「次相同区」[/color]

    [color=#7ca668]# $f[$j-1]是 ($j-1)的「次相同区」长度,等於 $len[/color]
    [color=#7ca668]# $len 是($j-1)「次相同区」长度,不是起点[/color]
    [color=#7ca668]# ($j-1)的「次相同区」内容为 $Key[0] 到 $Key[$len-1][/color]
    [color=#7ca668]# $j相同区 比 ($j-1)相同区多1字[/color]
    [color=#7ca668]# 用 「$j 相同区的最后1个字」 比对 $Key[$len][/color]
    [color=#7ca668]# 来确定此起点是否合适[/color]

    [color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){ [color=#7ca668]# ($j-1)「次相同区」起点合适[/color]
        [color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]
        [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]
        [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]

    }[color=#c586c0]else[/color]{ [color=#7ca668]# ($j-1)「次相同区」起点不合适[/color]

        [color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
            [color=#7ca668]# ($j-1)的「次相同区长度」不等於0[/color]
            [color=#7ca668]# 那麽就在($j-1)「次相同区」里面[/color]
            [color=#7ca668]# 寻找「次次相同区」的「起点」[/color]
            [color=#7ca668]# 把「次相同区长度」作为 $f[]的索引值[/color]
            [color=#7ca668]# 取得「次次相同区」长度[/color]

            [color=#7ca668]# 这里并没有去改变 $j 的值[/color]
            
            [color=#7ca668]# 在while的新一回合[/color]
            [color=#7ca668]# 会测试  $Key[$j-1] -eq $Key[次次相同区长度][/color]
            [color=#7ca668]# 确认「次次相同区」的「起点」是否合适[/color]

            [color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
        
        }[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]
            [color=#7ca668]# 可能1:[/color]
            [color=#7ca668]# ($j-1)的次相同区长度是0 [/color]
            [color=#7ca668]# $j 相同区 的最后1字 不等於 $Key[0][/color]
            [color=#7ca668]#[/color]
            [color=#7ca668]# 可能2:[/color]
            [color=#7ca668]# ($j-1)的次相同区长度不是0[/color]
            [color=#7ca668]# 但「次次相同区」or「次次次相同区」or 「次次次次相同区」是0[/color]
            [color=#7ca668]# $j 相同区 的最后1字 不等於 $Key[0][/color]
            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
            [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
        }
    }
}
[/color][/size][/font][/td][/tr]
[/table]


预先知道:移动后,马上就比对失败
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd]
   比对            移动后
[color=#9cdcfe]$i[/color] 0123456789     0123456789
  AACAA[b][color=#ff00ff]Q[/color][/b]AACAAC   AACAA[b][color=#ff00ff]Q[/color][/b]AACAAC
       X              X
  AA[b][color=#ff00ff]C[/color][/b]AA[b][color=#ff00ff]C[/color][/b]            AA[b][color=#ff00ff]C[/color][/b]AA[b][color=#ff00ff]C[/color][/b]
[color=#9cdcfe]$j[/color] 012345            012345

  比对失败位置: [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] 5
  「相同区」:AACAA
  「次相同区」:AA
  「次相同区」长度:2

  如果「次相同区」后面的字,和比对失败位置的字相同
  即,如果 [color=#9cdcfe]$Key[/color][[color=#b5cea8]2[/color]] 等於 [color=#9cdcfe]$Key[/color][[color=#b5cea8]5[/color]]
  移动后的第一次比对,马上就比对失败
[/color][/size][/font][/td][/tr]
[/table]

设定 $f[ ] 改良版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}

[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]

[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]

[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]]

[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){
    [color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
        [color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]

        [color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){ [color=#7ca668]# ok[/color]
            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]

        }[color=#c586c0]else[/color]{ [color=#7ca668]# 移动后,马上就比对失败[/color]

                [color=#7ca668]#在制表时,就先设定到最适合的次相同区长度[/color]
                [color=#7ca668]#避免正式比对时,多做额外的比对[/color]
            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
        }
        [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]

    }[color=#c586c0]else[/color]{
        [color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
            [color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]

        }[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]

            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
            [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
        }
    }
}
[/color][/size][/font][/td][/tr]
[/table]

nwm310 发表于 2020-10-11 12:17

KMP 字串搜寻演算法 - 最终版
[table=98%,#000000]
[tr][td][font=monospace][size=12px][color=#dddddd][color=#9cdcfe]$Text[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAQABAB'[/color]
[color=#9cdcfe]$Key[/color] [color=#d4d4d4]=[/color] [color=#ce9178]'ABAB'[/color]

[color=#7ca668]#======= 设定 $f[] ========[/color]
[color=#c586c0]if[/color] ([color=#9cdcfe]$Key.Length[/color] [color=#d4d4d4]-lt[/color] [color=#b5cea8]3[/color]){[color=#c586c0]throw[/color] [color=#ce9178]'$Key 长度太小'[/color]}

[color=#7ca668]#$f 是一个数组,它的长度和 $Key 一样[/color]
[color=#9cdcfe]$f[/color] [color=#d4d4d4]=[/color] [color=#569cd6]@[/color]([color=#b5cea8]0[/color]) [color=#d4d4d4]*[/color] [color=#9cdcfe]$Key.Length[/color]

[color=#9cdcfe]$f[/color][[color=#b5cea8]0[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]

[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]2[/color]
[color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#b5cea8]1[/color]]

[color=#c586c0]while[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Key.Length[/color]){
    [color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color][color=#d4d4d4]-[/color][color=#b5cea8]1[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
        [color=#9cdcfe]$len[/color][color=#d4d4d4]++[/color]

        [color=#c586c0]if[/color] ([color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]-ne[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$len[/color]]){
            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$len[/color]
        }[color=#c586c0]else[/color]{
            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]
        }
        [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]

    }[color=#c586c0]else[/color]{
        [color=#c586c0]if[/color] ([color=#9cdcfe]$len[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
            [color=#9cdcfe]$len[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$len[/color]]

        }[color=#c586c0]else[/color]{ [color=#7ca668]# $len -eq 0[/color]

            [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
            [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]
        }
    }
}

[color=#7ca668]#======= 开始寻找 ========[/color]
[color=#9cdcfe]$i[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]0[/color]
[color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#b5cea8]-1[/color]
[color=#c586c0]while[/color] ([color=#9cdcfe]$i[/color] [color=#d4d4d4]-lt[/color] [color=#9cdcfe]$Text.Length[/color]){
    [color=#c586c0]if[/color] ([color=#9cdcfe]$Text[/color][[color=#9cdcfe]$i[/color]] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key[/color][[color=#9cdcfe]$j[/color]]){
        [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
        [color=#9cdcfe]$j[/color][color=#d4d4d4]++[/color]

        [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-eq[/color] [color=#9cdcfe]$Key.Length[/color]){
            [color=#9cdcfe]$ans[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$i[/color] [color=#d4d4d4]-[/color] [color=#9cdcfe]$j[/color]
            [color=#c586c0]break[/color]
        }
    }[color=#c586c0]else[/color]{
        [color=#c586c0]if[/color] ([color=#9cdcfe]$j[/color] [color=#d4d4d4]-ne[/color] [color=#b5cea8]0[/color]){
            [color=#9cdcfe]$j[/color] [color=#d4d4d4]=[/color] [color=#9cdcfe]$f[/color][[color=#9cdcfe]$j[/color]]
        
        }[color=#c586c0]else[/color]{
            [color=#9cdcfe]$i[/color][color=#d4d4d4]++[/color]
        }
    }
}

[color=#c586c0]if[/color] ([color=#9cdcfe]$ans[/color] [color=#d4d4d4]-eq[/color] [color=#b5cea8]-1[/color]){
    [color=#ce9178]'没找到'[/color]
}[color=#c586c0]else[/color]{
    [color=#ce9178]"[/color][color=#9cdcfe]$Key[/color][color=#ce9178] 在 [/color][color=#9cdcfe]$ans[/color][color=#ce9178]"[/color]
}

[/color][/size][/font][/td][/tr]
[/table]

whiter 发表于 2021-9-4 21:41

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

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.