[Algorithm/문자열 탐색] KMP(Knuth–Morris–Pratt) 알고리즘

1. KMP(Knuth–Morris–Pratt) 알고리즘이란?

• 텍스트와 패턴 사이에 겹치는 부분을 찾아내 검사를 다시 시작할 위치를 구하여 패턴을 한번에 많이 옮기는 알고리즘이다.
• "몇번째 문자부터 다시 검색할지"에 대한 값을 미리 표로 만들어 검사를 시작할 위치를 구한다. 즉 패턴과 텍스트가 불일치할 경우, 그 전에 검사했던 텍스트의 문자를 표에 작성하여 불필요한 검사는 생략한다. 
• 시간 복잡도는 O(n)이다.

이미지 출처: https://res.cloudinary.com/practicaldev/image/fetch/s--sIuKzZP6--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://thepracticaldev.s3.amazonaws.com/i/v0zycstq7juyvsgx2u7i.jpg

2. 동작 방식

• skip[]은 패턴에서 접두사(prefix)와 접미사(suffix)가 일치하는 최대 길이를 저장하는 배열이다.
• 접두사와 접미사가 일치하지 않으면, 접미사를 가리키는 인덱스를 1 증가한다. 
• 접두사와 접미사가 일치하면, 접두사를 가리키는 인덱스와 접미사를 가리키는 인덱스를 1 증가한다.

문자열 ABAABAB를 예시로 들어보자

index	text	skip[index]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

 

3. 구현하기

static int kmpMatch(String text, String pattern) {
  int pt = 1; // text 커서
  int pp = 0; // pattern 커서
  int[] skip = new int[pattern.length() + 1]; // 건너뛰기 표

  // 건너뛰기 표 생성
  skip[pt] = 0;
  while(pt != pattern.length()) {
    if(pattern.charAt(pt) == pattern.charAt(pp)) {
      skip[++pt] = ++pp;
    } else if(pp == 0) {
      skip[++pt] = pp;
    } else {
      pp = skip[pp];
    }
  }
  
  // 문자열 검색
  pt = pp = 0;
  while(pt != text.length() && pp != pattern.length()) {
    if(text.charAt(pt) == pattern.charAt(pp)) {
      pt++;
      pp++;
    } else if(pp == 0) {
      pt++;
    } else {
      pp = skip[pp];
    }
  }
  
  if(pp == pattern.length()) {
    // 패턴의 모든 문자 대조
    return pt - pp;
  } else {
    // 검색 실패
    return -1;
  }
}