1

我正在玩 f sharp 中的 KMP 算法。虽然它适用于 "ATAT" 之类的模式（结果将是 [|0; 0; 1; 2;|]），但当字符串的前 2 个字符相同且第三个字符是另一个时，第一个 while 循环进入死锁，例如“AAT”。

我明白为什么：首先，i 递增到 1。现在 while 循环的第一个条件为真，而第二个条件也为真，因为“A”<>“T”。现在它将 i 设置为 prefixtable.[!i]，它又是 1，我们开始吧。

你们能给我一个关于如何解决这个问题的提示吗？

let kMPrefix (pattern : string) = 

    let (m : int) = pattern.Length - 1
    let prefixTable = Array.create pattern.Length 0
    // i : longest proper prefix that is also a suffix 
    let i = ref 0

    // j: the index of the pattern for which the prefix value will be calculated
    // starts with 1 because the first prefix value is always 0

    for j in 1 .. m do

        while !i > 0 && pattern.[!i] <> pattern.[j] do

            i := prefixTable.[!i]

        if pattern.[!i] = pattern.[j] then

            i := !i+1           


        Array.set prefixTable j !i  

    prefixTable
4

1 回答 1

3

我不确定如何通过小修改来修复代码，因为它与 KMP 算法的查找表内容不匹配（至少是我在 Wikipedia 上找到的内容），它们是：

  • -1 表示索引 0
  • 否则，当前位置之前匹配开头的连续元素的计数（不包括开头本身）

因此，我希望输出为"ATAT"，而[|-1; 0; 0; 1|]不是[|0; 0; 1; 2;|]。

这种类型的问题可能更好地用函数式来推理。要创建 KMP 表，您可以使用递归函数逐个填充表，跟踪有多少最近的字符与开头匹配，并在第二个字符的索引处开始运行它。

一个可能的实现：

let buildKmpPrefixTable (pattern : string) =
    let prefixTable = Array.zeroCreate pattern.Length

    let rec run startIndex matchCount =
        let writeIndex = startIndex + matchCount
        if writeIndex < pattern.Length then
            if pattern.[writeIndex] = pattern.[matchCount] then
                prefixTable.[writeIndex] <- matchCount
                run startIndex (matchCount + 1)
            else
                prefixTable.[writeIndex] <- matchCount
                run (writeIndex + 1) 0
    run 1 0
    if pattern.Length > 0 then prefixTable.[0] <- -1
    prefixTable

这种方法没有任何无限循环/递归的危险，因为所有代码路径run要么writeIndex在下一次迭代中增加，要么完成迭代。

关于术语的注意事项：您在问题中描述的错误是无限循环，或者更一般地说是非终止迭代。死锁特指线程等待一个永远不会被释放的锁的情况，因为持有它的线程本身也在等待一个永远不会被释放的锁，出于同样的原因。

于 2016-08-19T10:32:28.110 回答