[문자열 매칭] KMP (knuth-morris-prett) 동작방식,수도코드

 
 

✅ 개요

문자열 매칭 알고리즘 중 O(N+M)을 보장하는, KMP 알고리즘의 원리를 알아보자. 
 
 
 

✅ 단순 문자열 매칭의 비효율

가장 단순하게 문자열 매칭을 해보면
아래와 같은 수도 코드가 된다.
 

 
2중 for문을 사용하게 되어서
만약 찾고자 하는 패턴이,  문자열의 마지막에 존재하게 되면    최악의 케이스는 O(N*M)이 된다. 
 
 
 
단순 문자열 비교는 너무나 비효율적이고, 
모든 경우를 다 비교하지 않기 위해 문자열 매칭 알고리즘들이 존재한다.
 
 
 
 

✅ KMP (Knuth-Morris-Pratt)

오늘 공부해볼 알고리즘은 KMP이다.
 
 
KMP는 접두사/접미사의 개념을 활용해
1) 모든 경우를 계산하지 않고
2) 반복되는 연산을 줄인다
 
 

 🕰 시간복잡도 : O(N+M)

• N : text 문자열의 길이
• M : 패턴 문자열의 길이

 

1️⃣ 테이블에 정보 저장

접두사이면서 접미사인 문자열의 최대 길이를 저장하는 테이블을 미리 정의한다.
(불일치가 발생했을때,,   패턴이 어디까지 일치했는지 보고,  다음 시작 위치를 말해주는 테이블이다.)
 

검색할 패턴이 abacaaba라고 가정했을 때 
각 index 까지   접두사이면서 접미사인 최대 길이를 배열에 저장한다

table[7]의 경우엔 abacaaba에서   
aba가 가장 긴   접두사이면서 접미사이므로
해당 길이인 3이 저장된다

 
 
 

2️⃣ 작동과정의 시각화

 
검색대상 문자열이 ababacabacaaba라고하고,
검색할 패턴이 abacaaba라고 가정하자. 
 
table에는 아까 저장한 0 0 1 0 1 1 2 3 이 저장되어있다.
 
수도 코드를 함께 보면서 이해하길 바란다.

 
✍️  pattern과 비교했을때,,  지금까지 몇개가 일치하는가?  -> idx 에 저장
for문 --  text의 길이만큼 반복을 한다.  
 
text의 처음부터 매칭을 시작한다. 
idx는 0인상태로 시작하고, 매칭 실패할때까지 idx는 1 증가한다.
 
첫번째 불일치는 idx 가 3인 상황에서 발생했다. 

idx는 0보다 크면서 불일치가 발생했으므로, 
table[idx-1]의 값을 idx로 넣는다 
 
 
확인해보면 table[3-1] = table[2]는 1인데
1이라는 값은 aba 라는 문자열이 접두사/접미사로 a 한개가 일치함을 의미하는 것이다. 
 
여기에서 idx를 1로 설정하면, b가 해당 idx로 변경되며, 앞에 부분의 매칭은 생략이 가능해진다.
 
(솔직히 확실히 와닿지는 않아서 이런식으로 작동한다는 개념을 받아들이는 느낌이다. 나중에 더 이해가 잘 되면 설명을 수정하러 와야겠다..)
 
 
 
다시 문자열 매칭을 시작한다. for문은 text만을 계속 반복하고 있기 때문에 이번에는 text[4]부터 시작해 매칭을 시도하게 된다.
두번째 불일치는 idx 가 5인 상황에서 발생한다.  

이때도 table[5-1] = table[4] = 1이므로
1이라는 값은 aba 라는 문자열이 접두사/접미사로 a 한개가 일치함을 의미하며,
여기에서 idx를 1로 설정하면, b가 해당 idx로 변경되며, 앞에 부분의 매칭은 생략이 가능해진다.
 
 
 
다시 문자열 매칭을 또 시작하고, idx가 7까지 간다. 
idx가 m-1 (문자열 길이 -1) 이 되는 순간 문자열을 발견한것이므로 탐색이 종료된다. 
 
 
 
 
완벽하게 이해된것은 아니지만 작동 방식을 머리로 이해하는데엔 충분했던것 같다
좀더 이해가 되면 정리를 더 잘할 수 있도록 노력해야겠다. 
 
 
 

✅ 한번에 볼수 있게 최종 버전 첨부

 
 
 
 

아래는 내가 참고한 블로그에 적혀있는 KMP 코드이다.

static void KMP(String parent, String pattern) {
	int[] table = makeTable(pattern);
		
	int n1 = parent.length();
	int n2 = pattern.length();
		
	int idx = 0; // 현재 대응되는 글자 수
	for(int i=0; i< n1; i++) {
		// idx번 글자와 짚더미의 해당 글자가 불일치할 경우, 
		// 현재 대응된 글자의 수를 table[idx-1]번으로 줄인다.
		while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
		// 글자가 대응될 경우	
		if(parent.charAt(i) == pattern.charAt(idx)) {
			if(idx == n2-1) {
				System.out.println(i-idx+1 + "번째에서 찾았습니다. ~" + (i+1) );
				idx =table[idx];
			}else {
				idx += 1;
			}
		}
	}
}

 
 

---

references 

https://loosie.tistory.com/192

[알고리즘] 문자열 매칭 알고리즘 KMP (Java)