F sharp KMP 알고리즘이 처음 두 indces에서 같은 문자로 패턴을 사용하는 경우 첫 번째 while 루프에 걸렸습니다.

Question

나는 KMP 알고리즘으로 날카롭게 놀고 있습니다. "ATAT"(결과는 [| 0; 0; 1; 2; |])와 같은 패턴에서 작동하지만 첫 번째 while 루프는 문자열의 처음 두 문자가 같고 세 번째 문자가 다른 경우 교착 상태가됩니다. 예 : "AAT".

왜 나는 먼저 1로 증가합니다. 이제는 "A"<> "T"이기 때문에 while 루프의 첫 번째 조건은 참이고 두 번째 조건도 참입니다. 이제 i를 접두사 테이블로 설정합니다. [! 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 알고리즘의 조회 테이블의 내용과 일치하지 않기 때문에, 작은 수정과 코드를 복구하는 방법을 잘 모르겠어요 : 0

그렇지 않으면 인덱스

• -1, 시작과 일치하는 현재 위치 전에 연속 요소의 수 따라서

(시작 자체를 제외), 나는 좋겠 "ATAT"의 출력이 [|0; 0; 1; 2;|]이 아니라 [|-1; 0; 0; 1|]이 될 것으로 예상하십시오.

이러한 유형의 문제는 기능적 스타일을 생각하는 것이 더 나을 수 있습니다. KMP 테이블을 만들려면 재귀 함수를 사용하여 테이블을 하나씩 채우고 최근 문자 수가 시작 부분과 일치하는지 확인한 다음 두 번째 문자 인덱스에서 실행하십시오.

가능한 구현 : run의 모든 코드 경로는 다음 반복에 writeIndex을 증가 시키거나 반복하는 마무리 하나 때문에

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 

이러한 접근 방식은 어떤 무한 루프/재귀의 위험이 없습니다.

참고 용어에 대한 설명 : 질문에서 설명하는 오류는 무한 루프이거나 더 일반적으로 비 종단 반복입니다. 교착 상태는 스레드가 잠금 해제를 기다리는 상황을 특히 참조합니다. 스레드가 스레드를 보유하고 있기 때문에 동일한 이유로 해제되지 않을 잠금을 기다리고 있기 때문입니다.