F sharp KMP Алгоритм застревает в первом цикле while, если я использую шаблон с теми же символами в первых двух указателях

Question

Я играю с алгоритмом KMP в f sharp. Хотя он работает для таких шаблонов, как «ATAT» (результат будет [| 0; 0; 1; 2; |]), первый цикл while входит в тупик, когда первые 2 символа строки являются одинаковыми, а третий - другой , например, «AAT».

Я понимаю, почему: во-первых, я получаю приращение до 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

Я не уверен, как восстановить код с небольшой модификацией, так как он не соответствует содержанию поиска таблицы КТИ выполняемого алгоритма (по крайней мере те, которые я нашел в Википедии), которые являются:

• -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 в следующей итерации или закончить итерации.

Замечание по терминологии: ошибка, которую вы описываете в вопросе, представляет собой бесконечный цикл или, в более общем плане, бесконечную итерацию. «Тупик» относится конкретно к ситуации, когда поток ждет блокировки, которая никогда не будет выпущена, потому что нить, в которой она находится, сама ждет блокировки, которая никогда не будет выпущена по той же причине.