크누스-모리스-프랫 알고리즘

크누스-모리스-프랫 알고리즘

학급	문자열 검색
data 구조	스트링
최악의 경우 성능	${\displaystyle \theta }$( m ) { $displaystyle$ \$Theta$( m$$ )$전처리{\displaystyle \mathrm{}}$ + ${\displaystyle (}$ ( $n ){ displaystyle$ \$Theta$( n )매칭$$[note 1]
최악의 경우 공간의 복잡성	${\displaystyle\Theta(m)}$

컴퓨터 과학에서 Knuth-Morris-Pratt 문자열 검색 알고리즘(또는 KMP 알고리즘)은 "단어"의 발생을 검색합니다.W주요 "텍스트 문자열" 내에서S미스매치가 발생했을 때 단어 자체가 다음 일치가 어디서 시작될 수 있는지를 판단하기에 충분한 정보를 구현한다는 관찰을 채택함으로써 이전에 일치한 문자의 재검사를 생략할 수 있다.

이 알고리즘은 James H. Morris에 의해 고안되었고 Donald Knuth에 의해 오토마타 ^[1][2]이론에서 독립적으로 발견되었다.Morris와 Vaughan Pratt는 ^[3]1970년에 기술 보고서를 발표했습니다.이들 3사는 ^[1]1977년 이 알고리즘을 공동 발표했다.1969년 마티야세비치는^[4][5] 2진수 알파벳에 대한 문자열 패턴 일치 인식 문제를 연구하던 중 2차원 튜링 기계에 의해 코드화된 유사한 알고리즘을 발견했다.이것은 문자열 ^[6]매칭을 위한 최초의 선형 시간 알고리즘입니다.

배경

문자열 일치 알고리즘이 시작 인덱스를 찾으려고 합니다.m줄을 서서S[]검색어와 일치하는W[].

"Brute-force" 또는 "Naive" 알고리즘으로 알려진 가장 간단한 알고리즘은 각 색인에서 일치하는 단어를 찾는 것입니다.m, 즉, 검색되는 문자열 내의 문자에 대응하는 위치S[m]각 위치에서m알고리즘은 먼저 검색되는 워드에서 첫 번째 문자의 동일성을 확인합니다.S[m] =? W[0]일치하는 것이 발견되면 알고리즘은 단어 위치 인덱스의 연속된 값을 체크하여 검색 대상 단어 내의 다른 문자를 테스트합니다.i알고리즘은 문자를 가져옵니다.W[i]검색되고 있는 단어에서 표현의 동일성을 체크한다.S[m+i] =? W[i]연속되는 모든 문자가 일치하는 경우W위치에m그러면 검색 문자열의 해당 위치에서 일치하는 항목이 검색됩니다.인덱스가m문자열 끝에 도달하면 일치하는 항목이 없습니다. 이 경우 검색이 "실패"라고 합니다.

일반적으로 평가판 체크는 평가판 일치를 빠르게 거부합니다.문자열이 랜덤으로 균등하게 분포되어 있는 경우 문자가 일치할 확률은 26분의 1입니다.대부분의 경우 평가판 검사에서는 첫 번째 서신에서 일치가 거부됩니다.처음 두 글자가 일치할 확률은 26분의² 1(676분의 1)입니다.따라서 문자가 랜덤인 경우 문자열 검색의 예상 복잡도는S[]길이 n은 n 비교 또는 O(n)의 순서입니다.기대했던 퍼포먼스가 아주 좋아요.한다면S[]100만 글자이고W[]1000자이므로 약 104만 문자의 비교 후에 문자열 검색이 완료됩니다.

기대했던 퍼포먼스는 보증되지 않습니다.문자열이 랜덤이 아닌 경우 평가판 확인m여러 가지 성격 비교가 필요할 수 있습니다.최악의 경우는 두 문자열이 마지막 문자를 제외하고 모두 일치하는 경우입니다.그 끈이 그 끈이S[]모두 A인 100만 글자로 구성되어 있습니다.W[]마지막 B자로 끝나는 999 A 문자입니다.간단한 문자열 일치 알고리즘은 각 시행 위치에서 1000자를 검사한 후 일치를 거부하고 시행 위치를 진행합니다.간단한 문자열 검색 예에서는 약 1000개의 문자 비교 곱하기 100만 개의 위치를 사용하여 10억 개의 문자를 비교합니다.의 길이가W[]최악의 퍼포먼스는 O(k⋅n)입니다.

KMP 알고리즘은 단순한 알고리즘보다 최악의 경우 성능이 우수합니다.KMP는 테이블을 사전 계산하는 데 약간의 시간을 소비합니다(대략W[], O(k)를 사용하여 O(n) 내의 문자열을 효율적으로 검색합니다.

차이점은 KMP는 단순한 알고리즘에서는 사용되지 않는 이전의 일치 정보를 사용한다는 것입니다.위의 예에서는 KMP가 1000번째 문자의 트라이얼 매칭에 실패했을 때(i= 999)의 이유S[m+999] ≠ W[999], 이 값이 증가합니다.m단, 새로운 위치의 첫 번째 998자가 이미 일치함을 알 수 있습니다.KMP는 1000번째 문자(위치 999)에서 불일치를 검출하기 전에 999A 문자와 일치했습니다.평가판 매치 포지션 진행m첫 번째 A를 폐기함으로써 KMP는 일치하는 998개의 A 문자가 있음을 알 수 있습니다.W[]테스트하지 않습니다.즉, KMP 세트는i998까지.KMP는 사전에 계산된 테이블과 2개의 상태 변수에 대한 지식을 유지합니다.KMP가 불일치를 검출하면 테이블에 따라 KMP의 증가량이 결정됩니다(변수).m테스트를 재개하는 장소(예:i).

KMP 알고리즘

검색 알고리즘의 예

알고리즘의 상세를 나타내려면 알고리즘의 (상대적으로 인위적인) 실행을 고려합니다.W= "ABCDABD" 및S= "ABC ABCDAB ABCDABDE"알고리즘은 항상 다음 2개의 정수에 의해 결정되는 상태가 됩니다.

• m(내부 위치를 나타냄)S장래의 경쟁 상대인 곳W시작합니다.
• i(현재 고려되고 있는 문자의 인덱스를 나타냅니다).W.

각 단계에서 알고리즘은S[m+i]와 함께W[i]및 증분i만약 그들이 같다면.이것은 실행이 시작될 때 다음과 같이 묘사됩니다.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

이 알고리즘은 다음 문자를 비교합니다.W글자를 '고정'하다S, 를 증가시켜, 1 에서 다음 순서로 이동한다.i일치한다면요.하지만 네 번째 단계에서는S[3] = ' '일치하지 않는다W[3] = 'D'. 에서 다시 검색을 시작하는 것이 아니라S[1]에 주의해 주십시오.'A'위치 1과 위치 2 사이에서 발생합니다.S그 때문에, 그 모든 문자를 사전에 체크(및 대응하는 문자와 일치하고 있는 것을 알고 있다)W)는, 매치의 개시점을 찾을 가능성이 없습니다.따라서 알고리즘은m = 3그리고.i = 0.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

이 일치는 첫 번째 문자에서 실패하기 때문에 알고리즘은m = 4그리고.i = 0

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

여기서,i거의 완전한 일치를 통해 증가하다"ABCDAB"까지i = 6에 불일치를 주는 것W[6]그리고.S[10]다만, 현재의 부분 매치가 종료되기 직전에, 그 서브스트링이 있었습니다."AB"새로운 매치의 시작일 가능성이 있기 때문에 알고리즘에서는 이 점을 고려해야 합니다.이러한 문자는 현재 위치보다 앞의 두 문자와 일치하므로 다시 확인할 필요가 없습니다.알고리즘 세트m = 8(첫 번째 프레픽스의 시작) 및i = 2(처음 두 문자가 일치하는지 확인) 및 조회를 계속합니다.따라서 알고리즘은 이전에 일치한 문자를 생략할 뿐만 아니라S(the)"AB")과(와)가 일치합니다.W(프리픽스)"AB").

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

새 위치에서의 이 검색은 다음과 같은 이유로 즉시 실패합니다.W[2](a)'C')가 일치하지 않습니다.S[10](a)' '첫 번째 시행과 마찬가지로 불일치에 의해 알고리즘은 첫 번째 시행으로 돌아갑니다.W일치하지 않는 문자 위치에서 검색을 시작합니다.S:m = 10, 리셋i = 0.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

의 시합m=10즉석에서 실패하기 때문에 알고리즘은 다음 번을 시도합니다.m = 11그리고.i = 0.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

다시 한 번 알고리즘은"ABCDAB"하지만 다음 캐릭터는'C', 마지막 문자와 일치하지 않습니다.'D'그 말의W이전과 같은 추론, 알고리즘 설정m = 152글자 문자열로 시작합니다."AB"현재 위치로 연결, 설정i = 2현재 위치에서 조회를 계속합니다.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABDE W: ABCABD i: 0123456

이번에는 매치가 완료되어 매치의 첫 번째 캐릭터는S[15].

검색 알고리즘의 의사 코드 설명

위의 예에는 알고리즘의 모든 요소가 포함되어 있습니다.현재로서는 "부분 일치" 테이블이 존재한다고 가정합니다.T다음 설명에서는 불일치가 발견되었을 때 새로운 일치의 시작을 찾아야 하는 위치를 나타냅니다.의 엔트리T매치할 수 있도록 구축되어 있습니다.S[m]그것은 비교에 실패한다.S[m + i]로.W[i]다음 가능한 일치가 인덱스에서 시작됩니다.m + i - T[i]에S(즉,T[i]미스매치 후에 실행할 필요가 있는 「백트래킹」의 양입니다.여기에는 두 가지 의미가 있습니다.첫 번째는T[0] = -1이것은, 다음의 경우에,W[0]미스매치입니다.백트래킹은 할 수 없고 다음 문자를 체크하기만 하면 됩니다.둘째, 가능한 다음 일치는 인덱스에서 시작됩니다.m + i - T[i]위의 예시와 같이 실제로 체크할 필요는 없습니다.T[i]그 뒤에 나오는 캐릭터들을 계속 검색해서W[T[i]]다음은 KMP 검색 알고리즘의 의사 코드 구현 예를 나타냅니다.

알고리즘 kmp_search: 입력: 문자 배열, S(검색 대상 텍스트) 배열, W(요구된 단어) 출력: 정수 배열, P(W가 발견되는 S의 정수) 배열, nP(위치 수)는 변수를 정의한다: 정수, j ← 0(현재 c의 위치).Haracter S의)정수(W의 현재 성격의 위치)의 정수의 배열, TnP ← 0는 동안 j개체자(식탁 위, 다른 곳에서 계산된)만약 W[k])S[j] 다음 jj+1자 k← k+1만약 k=length(W) 다음(발생 발견되기만 한다면 처음 발생 ← k, length(S)니 0←.는필요한 경우, m ← j - k를 반환할 수 있음) P[nP] ← j - k, nP ← nP + 1 let k ← T[k] (T[length(W)]는 -1일 수 없음) 또는 k < 0일 경우 k ← T[k]로 한다.

검색 알고리즘의 효율성

테이블의 이전 존재를 가정할 때T , Knuth-Morris-Pratt 알고리즘의 검색 부분은 복잡도 O(n)를 가집니다.여기서 n은 의 길이입니다.SO는 big-O 표기법입니다.함수 입력 및 종료 시 발생하는 고정 오버헤드를 제외하고 모든 계산은 에서 수행됩니다.while루프. 이 루프의 반복 횟수를 제한하려면T같은 시기에 시작된 매치가S[m]비교 중에 실패하다S[m + i]로.W[i]다음 가능한 일치는 에서 시작해야 합니다.S[m + (i - T[i])]특히 다음 가능한 일치는 다음보다 높은 지수로 발생해야 합니다.m,하도록T[i] < i.

이 사실은 루프가 루프의 2개의 분기 중 하나를 반복할 때마다 실행하기 때문에 루프는 최대 2n회까지 실행될 수 있음을 의미합니다.첫 번째 분기는 변함없이 증가합니다.i변경되지 않습니다.m인덱스가m + i현재 면밀히 조사되고 있는 특징의S증가했습니다.두 번째 브랜치는 다음과 같이 추가합니다.i - T[i]로.m그리고 우리가 봤듯이, 이것은 항상 양수이다.그 때문에, 장소는m현재 잠재 매치의 시작 부분이 증가합니다.동시에 두 번째 브랜치는m + i변경되지 않음, 대상m얻다i - T[i]그 직후에 추가되었다.T[i]새로운 값으로 할당되다i,이런 이유로new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i이제 루프가 종료됩니다.m + i= n. 따라서 루프의 각 분기는 최대 n번까지 도달할 수 있는데, 이는 각각 다음 중 하나가 증가하기 때문이다.m + i또는m,그리고.m ≤ m + i: 만약m= n 그럼 확실히m + i§ n, 따라서 최대 단위 증가량만큼 증가하기 때문에, 우리는 반드시 다음을 가지고 있어야 한다.m + i= 과거 어느 시점에서든 n. 따라서 어느 쪽으로든 우리는 끝납니다.

따라서 루프는 최대 2n회 실행되며 검색 알고리즘의 시간 복잡도는 O(n)임을 나타냅니다.

다음은 런타임에 대해 생각할 수 있는 다른 방법입니다.우리가 일치하기 시작했다고 칩시다.W그리고.S위치에i그리고.p.한다면W서브스트링으로서 존재하다S그럼 p시에W[0..m] = S[p..p+m]성공했을 때, 즉 단어와 텍스트가 위치에서 일치합니다.W[i] = S[p+i]), 증가i1. 실패했을 때, 즉 단어와 텍스트가 위치에서 일치하지 않는 경우(W[i] ≠ S[p+i]텍스트 포인터는 정지된 상태로 유지되며 워드 포인터는 일정량 롤백됩니다( ).i = T[i],어디에T점프 테이블)을 사용하여W[T[i]]와 함께S[p+i]. 의 최대 롤백 횟수i에 의해 경계되어 있다.i즉, 어떤 장애가 발생하더라도 장애까지 진행된 만큼만 롤백할 수 있습니다.그러면 실행 시간이 2n인 것이 분명합니다.

"부분 일치" 테이블(일명 "실패 함수")

이 표의 목적은 알고리즘이 다음 문자와 일치하지 않도록 하는 것입니다.S한 번이 아닙니다.이를 가능하게 하는 선형 검색의 본질에 대한 중요한 관찰은 패턴의 초기 세그먼트에 대해 메인 문자열의 일부 세그먼트를 체크할 때 현재 위치보다 먼저 새로운 잠재적 일치가 시작될 수 있는 위치를 정확히 알고 있다는 것입니다.즉, 패턴 자체를 「사전 검색」해, 가능한 모든 폴백 위치의 리스트를 작성합니다.이 리스트에서는, 최대 가망 없는 문자를 바이패스 해, 일치할 가능성이 있는 문자는 바이패스 할 수 없습니다.

각 포지션별로 위를 볼 수 있기를 바랍니다.W의 가장 긴 초기 세그먼트의 길이W(포함하지 않고) 그 위치에 도달하는 것, 그 위치에서 시작하는 풀 세그먼트 이외의 것W[0]이 정도로 되돌아가야 다음 일치를 찾을 수 있습니다.이런 이유로T[i]가장 길고 적절한 초기 세그먼트의 길이입니다.W이것은 또한 로 끝나는 서브스트링의 세그먼트입니다.W[i - 1]. 빈 문자열의 길이가 0이라는 규칙을 사용합니다.패턴의 시작 부분에서 불일치는 특수한 경우이므로(백트랙 가능성이 없음),T[0] = -1이하에 설명하겠습니다.

테이블 빌드 알고리즘의 작업 예

의 예를 검토하겠습니다.W = "ABCDABD"먼저, 메인 검색과 거의 같은 패턴을 따르고, 비슷한 이유로 효율적이라는 것을 알 수 있을 것이다.설정했습니다.T[0] = -1.찾기 위해서.T[1], 우리는 적절한 접미사를 발견해야 합니다."A"패턴의 접두사이기도 합니다.W. 그러나 적절한 접미사가 없습니다."A", 그래서 우리는T[1] = 0.찾기 위해서.T[2]서브스트링은W[0]-W[1]("AB")에 적절한 서픽스가 있습니다."B"단, "B"는 패턴의 접두사가 아닙니다.W그러므로, 우리는T[2] = 0.

에의 속행하다T[3]먼저 길이 1의 적절한 서픽스를 체크합니다.앞의 경우와 같이, 이 서픽스는 실패합니다.더 긴 접미사도 확인해볼까요?아니요, 모든 서픽스를 체크하기 위한 숏컷이 있습니다.예를 들어 적절한 프레픽스(스트링의 적절한 프레픽스는 문자열 자체와 동일하지 않습니다)가 검출되어 에서 종료한다고 합시다.W[2]길이가 2(가능한 최대)인 경우 첫 번째 문자는 적절한 프레픽스이기도 합니다.W따라서 적절한 프레픽스 자체이며, 여기서 끝납니다.W[1](이러한 것은 이미 판명된 바와 같이 발생하지 않았습니다.T[2] = 0가 아니라T[2] = 1따라서 각 단계에서 m사이즈의 유효한 접미사가 이전 단계에서 발견된 경우에만 m+1사이즈의 접미사를 체크하는 것을 고려해야 한다는 것이 바로 가기 규칙입니다.T[x] = mm+2, m+3 등을 체크할 필요가 없습니다.

따라서 길이가 2인 기판도 신경 쓸 필요가 없고, 이전과 마찬가지로 길이가 1인 기판만 고장났기 때문에,T[3] = 0.

다음 단계로 넘어갑니다.W[4],'A'같은 논리는 고려해야 할 가장 긴 서브스트링의 길이가1인 것을 나타내고 있습니다.앞의 경우와 마찬가지로 "D"는 다음 프레픽스가 아니기 때문에 실패합니다.W. 하지만 설정 대신T[4] = 0라고 하는 점에 주의하는 것으로, 보다 좋은 결과를 얻을 수 있습니다.W[4] = W[0], 그리고 그 검색은T[4]대응하는 것을 암시하다S성격,S[m+4]는 불일치이기 때문에S[m+4] ≠ 'A'따라서 검색을 다시 시작하는 것은 의미가 없습니다.S[m+4]1위부터 시작해야 한다.이것은 우리가 패턴을 바꿀 수 있다는 것을 의미한다.W일치 길이에 한 글자를 더하면 됩니다.T[4] = -1.

다음 캐릭터를 생각해보면W[5],어느 것이'B': 단, 검사 결과 가장 긴 서브스트링은 다음과 같습니다.'A', 우리는 여전히T[5] = 0이 추론은 왜 그런지와 비슷하다.T[4] = -1.W[5]프리픽스 조회를 확장합니다.W[4]에 대응하는 문자는,S,S[m+5] ≠ 'B'그래서 예전으로 되돌아가서W[5]무의미하지만S[m+5]아마도요.'A',이런 이유로T[5] = 0.

마지막으로 진행 중인 세그먼트의 다음 캐릭터는 다음과 같습니다.W[4] = 'A'되지요'B'그리고 이것도 역시W[5]게다가 위와 같은 주장은 우리가 미리 볼 필요가 없다는 것을 보여준다.W[4]코너를 찾다W[6]그래서 이렇게 해서T[6] = 2.

따라서 다음 표를 작성합니다.

또 다른 예는 다음과 같습니다.

다른 예(앞의 예와 약간 다릅니다)

또 다른 복잡한 예는 다음과 같습니다.

테이블 빌드 알고리즘의 의사 코드 설명

위의 예는 최소한의 소란으로 테이블을 조립하는 일반적인 방법을 보여줍니다.원칙은 전체적인 검색입니다.대부분의 작업은 이미 현재 위치에 도달하는 과정에서 이루어졌기 때문에, 그것을 떠나는 데 필요한 작업은 거의 없습니다.유일한 사소한 문제는 스트링의 마지막 부분에서 올바른 로직이 처음에 적절하지 않은 서브스트링을 잘못 제공한다는 것입니다.여기에는 초기화 코드가 필요합니다.

알고리즘 kmp_table: 입력: 문자 배열, W(분석 대상 단어) 출력: 정수 배열, T(채우는 테이블)는 변수를 정의한다: 정수, pos ← 1(현재 T에서 계산하고 있는 위치) 정수, cnd ← 0(현재 c의 다음 문자의 W에서 0에 근거한 인덱스).Andidate 서브스트링)은 Pos < length(W)가 W[pos] ← W[cnd]이면 T[pos] ← T[cnd]이면 T[pos] ← cnd로 하고, Cnd c 0 및 W[pos] ≠ W[cnd로 합니다.

테이블 빌드 알고리즘의 효율성

테이블 알고리즘의 시간(및 공간)의 $복잡도$는${\displaystyle }$O$)\displaystyle$ O$(k$입니다.$여기$서$$k(\$displaystyle$ k$)$는 다음 길이의W.

• 외부 루프:pos1로 초기화되어 있습니다.루프 상태는pos < k,그리고.pos루프가 반복될 때마다 1씩 증가합니다.따라서 루프는 k${\displaystyle }$-$$ {$style k-1}$회$$ $반복$됩니다.

• 내부 루프:cnd에 초기화되어 있다0외부 루프가 반복될 때마다 최대 1씩 증가합니다. T[cnd]항상 보다 작다cnd,그렇게cnd각 내부 루프 반복 시 최소1 감소합니다.내부 루프 조건은 다음과 같습니다.cnd ≥ 0즉, 내부 루프는 외부 루프가 실행한 횟수만큼 모두 실행할 수 있습니다.각각의 감소는cnd내부 루프에서 1만큼 증가해야 합니다.외부 루프는 k${\displaystyle }$-$$({$style k-1}$회$$ 반복)이므로 내부 루프는 총 k${\displaystyle }$-$$({$displaystyle k-1}$회)$회$까지만 반복할 수 있습니다.

외부 및 내부 루프를 모두 합치면 $최대{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{2k}}$- $(디스플레이$ 스타일 $2k-2)$의 반복이 소요됩니다.이는 Big O 표기법을 사용하는 O$)\displaystyle$ O$(k)}$ 시간$$ 복잡도에 $해당$합니다.

KMP 알고리즘의 효율성

알고리즘의 두 부분이 각각 복잡하기 때문에O(k)그리고.O(n)전체 알고리즘의 복잡성은 다음과 같습니다.O(n + k).

이러한 복잡성은 반복 패턴의 수에 관계없이 동일합니다.W또는S.

변종

KMP의 실시간 버전은 알파벳 문자별로 별도의 장애 함수 테이블을 사용하여 구현할 수 있습니다.텍스트의 $문자{\displaystyle }$x(\$displaystyle$ x$)$에서 불일치가 발생하면 문자$$x(\$displaystyle$ x$)$의 실패 함수 테이블에서 불일치가 발생한 패턴의 $색인{\displaystyle }$i(\$display$ i$)$를 참조합니다.그러면$$패턴의 프리픽스와 $일치$하는 $가장$ 긴 서브스트링의 길이가 반환되고 프리픽스 뒤의 문자가 x$({displaystyle$x$\})$라는 조건이 추가됩니다.이 제한에 의해 $텍스트$의$$문자 x({$displaystyle$x})는$$ 다음 단계에서 다시 체크할 필요가 없기 때문에 다음 단계에서만 체크됩니다.텍스트의^{[citation needed]} 각 인덱스의 처리 사이에 일정한 수의 연산이 실행된다.이는 실시간 컴퓨팅의 제약을 충족합니다.

Booth 알고리즘은 사전 편집상 최소 문자열 회전을 찾기 위해 수정된 버전의 KMP 전처리 함수를 사용합니다.실패 함수는 문자열이 회전할 때 점진적으로 계산됩니다.

메모들

레퍼런스

• Cormen, Thomas; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 32.4: The Knuth-Morris-Pratt algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 923–931. ISBN 0-262-03293-7. Zbl 1047.68161.
• Crochemore, Maxime; Rytter, Wojciech (2003). Jewels of stringology. Text algorithms. River Edge, NJ: World Scientific. pp. 20–25. ISBN 981-02-4897-0. Zbl 1078.68151.
• Szpankowski, Wojciech (2001). Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. pp. 15–17, 136–141. ISBN 0-471-24063-X. Zbl 0968.68205.

외부 링크

Wikibook Algorithm 구현에는 문자열 검색/Knuth-Morris-Pratt 패턴 매처라는 항목이 있습니다.

• 문자열 검색 애플릿 애니메이션
• David Eppstein의 알고리즘 및 샘플 C++ 코드 설명
• Knuth-Morris-Pratt 알고리즘 설명 및 Christian Charras와 Tierry Lecroq의 C 코드
• FH Flensburg에 의한 알고리즘의 처음부터 설명.
• Chu-Cheng Hsieh의 KMP 실행 단계를 분석합니다.
• NPTELHRD YouTube 강의 동영상
• Logic First YouTube 강의 동영상
• 정확성 증명
• 다른 형식의 알고리즘 간 변환
• C#로 작성된 Knuth-Morris-Pratt 알고리즘
• Knuth-Morris-Pratt 문자열 검색 알고리즘(파트 I) + CBMC, Knuth-Morris-Pratt 문자열 검색 알고리즘(파트 II): DFA 버전, Knuth-Morris-Pratt 문자열 검색 알고리즘(파트 III): DFA-less 버전