Knuth-Morris와 Pratt는 문자열 일치 문제에 대한 선형 시간 알고리즘을 소개합니다. O(n)의 매칭 시간은 매칭될 패턴 'p'의 일부 요소와의 비교에 이전에 포함되었던 'S'의 요소와의 비교를 회피함으로써 달성된다. 즉, 문자열 'S'에 대한 역추적은 절대 발생하지 않습니다.
KMP 알고리즘의 구성요소:
1. 접두사 기능(Π): 패턴에 대한 접두사 함수 Π는 패턴이 자체 이동과 어떻게 일치하는지에 대한 지식을 캡슐화합니다. 이 정보는 패턴 'p'의 쓸모없는 이동을 방지하는 데 사용될 수 있습니다. 즉, 문자열 'S'의 역추적을 방지할 수 있습니다.
2. KMP 경기: 문자열 'S', 패턴 'p' 및 접두사 함수 'Π'를 입력으로 사용하여 'S'에서 'p'의 발생을 찾고 발생이 발견된 후 'p'의 시프트 수를 반환합니다.
접두사 기능(Π)
다음 의사 코드는 접두사 함수 Π를 계산합니다.
<strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
실행 시간 분석:
접두사 함수를 계산하기 위한 위 의사 코드에서 4단계부터 10단계까지의 for 루프는 'm'번 실행됩니다. 1단계부터 3단계까지는 일정한 시간이 걸립니다. 따라서 접두사 함수를 계산하는 실행 시간은 O(m)입니다.
예: 아래 패턴 'p'에 대해 Π를 계산합니다.
SQL 카운트 고유
해결책:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
6번 반복한 후 접두사 함수 계산이 완료됩니다.
KMP는 다음과 일치합니다.
패턴 'p', 문자열 'S' 및 접두사 함수 'Π'를 입력으로 사용하는 KMP 일치 프로그램은 S에서 p 일치 항목을 찾습니다. 다음 의사 코드는 KMP 알고리즘의 일치 구성 요소를 계산합니다.
<strong>KMP-MATCHER (T, P)</strong> 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [q] // look for the next match
실행 시간 분석:
5단계에서 시작하는 for 루프는 'n'번, 즉 문자열 'S'의 길이만큼 실행됩니다. 1단계부터 4단계까지는 일정한 시간이 걸리므로 루프의 실행 시간은 이 시간에 의해 지배됩니다. 따라서 매칭 함수의 실행 시간은 O(n)입니다.
예: 다음과 같이 문자열 'T'와 패턴 'P'가 주어지면:
'T'에 'P'가 나타나는지 알아보기 위해 KMP 알고리즘을 실행해 보겠습니다.
'p'의 경우 접두사 함수, ? 이전에 계산되었으며 다음과 같습니다.
해결책:
Initially: n = size of T = 15 m = size of P = 7
패턴 'P'는 문자열 'T'에서 복잡도가 발생하는 것으로 확인되었습니다. 일치 항목을 찾기 위해 발생한 총 교대 횟수는 i-m = 13 - 7 = 6 교대입니다.