如果我在前两个索引处使用具有相同字符的模式，F sharp KMP 算法将卡在第一个 while 循环中

Question

我正在研究 f sharp 中的 KMP 算法。虽然它适用于像 "ATAT" 这样的模式（结果将是 [|0; 0; 1; 2;|]），但当字符串的前 2 个字符相同且第 3 个字符相同时，第一个 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

Answer 1

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

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

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

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

可能的实现：

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

这种方法没有任何无穷无尽 loops/recursion 的危险，因为 run 的所有代码路径在下一次迭代中增加 writeIndex 或完成迭代。

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

如果我在前两个索引处使用具有相同字符的模式，F sharp KMP 算法将卡在第一个 while 循环中

F sharp KMP Algorithm is stuck in the first while loop if i use a pattern with the same characters at the first two indces

f#

knuth-morris-pratt