[문자열 검색] KMP 알고리즘

단순하게 문자열을 찾는 방법을 생각해 보면 한 칸씩 비교해가며 일치하는지 확인하는 방법이 있다.

ABABABC에서 ABAB가 몇 번 들어가는지 확인하는 예시이다.

⇒ 일치

⇒ 불일치

⇒ 일치

⇒ 불일치

위와 같은 방식으로 찾게 되면 전체 문자열(len = N)에서 찾고자 하는 문자열(len = M)을 하나씩 비교해야 하므로 $O(NM)$의 시간복잡도를 갖게되어 비효율적인 알고리즘이 된다.

하지만, KMP 알고리즘을 사용하게 되면 시간복잡도가 $O(N+M)$으로 획기적으로 줄어들게 된다.

먼저 KMP 알고리즘을 배우기 전에 접두사와 접미사의 개념에 대해 알아야 한다.

예를 들어, apple의 접두사(prefix)는

app

appl

apple

접미사(subfix)는

ple

pple

apple

이렇게 접두사는 앞에서부터 순서대로 자르고, 접미사는 뒤에서부터 잘라 구하면 된다고 생각하면 된다.

다음으로, 접두사와 접미사를 사용해 문자열 검색시 불필요한 부분을 넘기기 위해 사용되는 pi배열을 만들어야 한다

pi[i]란 문자열의 0 ~ i까지에서 prefix == subfix 인 길이를 구해놓은 배열이다.

문자열 ABABC의 pi배열을 구하는 예시 통해 보자

❓ 왜 접두사와 접미사가 같은 경우를 PI 배열로 둘까?

문자열 ABABABC에서 pattern 문자열인 ABABC을 찾는다고 가정해 보자.

index가 4인 경우에서 일치하지 않게 되어 다음 index부터 탐색해야하지만, 1인 경우로 넘어가는 것은 불필요하다.

이런 경우 pi배열이 사용된다.

4에서 달랐다면 i = 3인 경우까지는 일치하다는 의미가 된다.

단순히 패턴 index 한 칸 옮겨 다시 검사하는 것이 아닌 pattern 문자열의 접두사와 접미사가 같은 부분까지 넘겨 버린다면 효율성이 증가하게 되는 것이다!

💻 KMP 구현하기

// parent: 전체 문자열, pattern: 찾고자하는 문자열
public ArrayList<Integer> kmp(String parent, String pattern) {
  // 문자열을 찾은 인덱스를 저장할 list
  ArrayList<Integer> list = new ArrayList<>();
  
  // pi배열을 생성
  int[] pi = getPi(pattern);

  int n = parent.length(), m = pattern.length();

  int j = 0; // i: 전체 문자열의 index, j: 패턴 문자열의 index
  for (int i = 0; i < n; i++) {
    while (j > 0 && parent.charAt(i) != pattern.charAt(j))
    	j = pi[j - 1];

    if (parent.charAt(i) == pattern.charAt(j)) {
    	// m은 패턴의 길이, 길이와 j가 같다면 패턴을 모두 찾은 경우
        if (j == m - 1) {
        
            // 문자열에서 패턴이 시작한 인덱스를 계산해 list.add
            list.add(i - m + 1);
            j = pi[j];
            
    	} else j++;
    }
  }

  return list;
}

while (j > 0 && parent.charAt(i) != pattern.charAt(j))
  j = pi[j - 1];

이 알고리즘에서 가장 핵심이 되는 부분이다. 문자열과 패턴이 일치하지 않는다면 pi만큼 건너 뛰게 한다.

j까지 패턴이 일치했으므로 pi[j - 1]을 통해 j값을 변경시켜주고,

while을 통해 parent[i]와 pattern[j]가 일치할 때까지 반복시켜준다.

🥧 pi배열 구현하기

public int[] getPi(String pattern) {
  int m = pattern.length();
  int[] pi = new int[m];

  int j = 0;
  for (int i = 1; i < m; i++) {
    while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
      j = pi[j - 1];

    if (pattern.charAt(i) == pattern.charAt(j))
      pi[i] = ++j;
  }

  return pi;
}

pi배열은 KMP 함수와 유사하게 구현이 가능하다.

단계별로 보며 어떻게 구성되는지 알아보자.

pattern = 'ABABABC'의 경우이다.