문자열 검색 KMP 알고리즘 :: 마이구미

이번 글은 KMP 알고리즘에 대해 다룰 것이다.

KMP 알고리즘이란 무엇인가?

이름에 대해서는 큰 의미가 없다. 그냥 사람 이름이다.

백준 5525번, 10769번, 1786번을 풀다가 알게 된 알고리즘이다.

유용한 알고리즘이기에 한명이라도 더 알리기 위해 글로 다루게 되었다. (복습 목적이지만..^^)

그렇다면 어떤 알고리즘인가? 어떤 경우에 사용하는 알고리즘인가?

시작해보자.

시작하기에 앞서 목적은 문자열 검색에 사용되는 알고리즘이다.

문자열 검색의 예를 들어보자.

문자열 ABCEDFRIEPQJDNVABRIDFNIABC 라는 문자열이 있을 때 ABCEF라는 문자열을 찾아보자.

여러분들은 어떻게 하겠는가?

가장 순진한 방법을 말해보겠다.

ABCEDABCEFQJDNVABRIDFNIABC 
ABCEF
ABCEDFRIEPQJDNVABRIDFNIABC
  ABCEF
ABCEDFRIEPQJDNVABRIDFNIABC
    ABCEF
ABCEDFRIEPQJDNVABRIDFNIABC
        ABCEF

가장 기본적으로 위와 같이 한자리씩 이동하면서 비교하는 방법을 사용할 수 있다.

이러한 방법을 이용하면 보다시피 문자열이 길어질수록 비교횟수가 훨씬 더 증가하는 것을 알 수 있다.

빅오표기법으로 O(전체 문자열 크기*찾을 문자열 크기) 이 될 것이다.

이를 해결하기 위한 방법이 KMP 알고리즘을 이용할 수 있다.

KMP 알고리즘을 이용할 시 O(문자열 크기 + 찾을 문자열 크기) 로 처리할 수 있다.

그렇다면 이제 KMP 알고리즘에 대해 본격적으로 알아보자.

일단 어떤 식으로 돌아가는 지 수박 겉을 핥아보자.

기본적인 방법처럼 문자열을 한자리씩 옮기면서 비교하면서 어떻게 하면 불필요한 부분을 넘길 수 있을까?

KMP 알고리즘의 핵심은 이전에 비교한 정보를 활용하여 검색하는 것이다.

예를 들어보자. 

ABCDABCDABEE에서 ABCDABE를 찾을 경우를 보자.
ABCDAB 까지는 동일하지만 마지막 요소가 다르다.
이 경우 기본적인 방법의 경우에는 다시 한자리를 증가하여 비교하게 된다.
KMP 알고리즘의 경우에는 ABCDAB까지 같았다는 정보를 가지고 그 다음 비교를 정하게 된다.

KMP 알고리즘을 알기 위해선 기본적으로 접두사와 접미사의 개념이 필요하다.

간단하게 접두사란 앞에 붙이는 단어, 접미사란 뒤에 붙이는 단어라고 찾아볼 수 있을 것이다.

예를 들어보자.

ABCDAB

접두사 - A, AB, ABC, ABCD, ABCDA, ABCDAB

접미사 - B, BA, BAD, BADC, BADCB, BADCBA

그냥 접두사는 앞에서부터 잘랐고, 접미사는 뒤에서부터 잘랐다.

그렇다면 0~i까지 문자열 중 접미사와 접두사가 같을 경우의 가장 긴 길이를 구할 것이다.

아래의 예를 보면서 이해를 해보자.

AAABAA

A - 0

AA - 1

AAA - 2

AAAB - 0

AAABA - 1

AAABAA - 2

ABCDAB

A - 0

AB - 0

ABC - 0

ABCD - 0

ABCDA - 1

ABCDAB - 2

이것을 활용하여 불필요한 부분을 넘길 때 사용하는 PI라는 배열을 만들 것이다.

여기서 의문이 들 수도 있다.

왜 접미사와 접두사가 같은 경우를 조건으로 들까?

불필요한 부분을 넘길 때에 주의할 점은 넘기고 그 전에 찾을 문자열이 포함된 것이 있는지 한번 확인해봐야한다.

예를 들면, AAAABAAAAC 문자열에서 AAAAC를 찾을 땐 인덱스 4에서 같지 않으니 그냥 바로 인덱스 5로 넘겨 비교하면 된다.

그래서 그냥 같지 않다 싶으면 찾을 문자열 크기만큼 인덱스를 넘겨버리면 되겠다 생각할 수 있다.

AAAABAAAAC
=> 크기만큼 건너뛰기
AAAABAAAAC

하지만 예외가 발생한다.

ABCDABCDABEAAAA 문자열에서 ABCDABE를 찾을 경우에는 인덱스 6에서 틀리기 때문에, 크기만큼 넘겨보자.

ABCDABCDABEAAAA
=> 크기만큼 건너뛰기
ABCDABCDABEAAAA

인덱스 6 전에 인덱스 4,5의 요소 AB라는 녀석 => 찾을 문자열에 포함되는 녀석이 있다.

무작정 크기를 통해 넘기면 안되는 것을 확인했다.

그렇기 때문에 접두사와 접미사가 같은 것을 기준으로 PI배열을 만드는 것이다.

그렇다면 kmp 알고리즘 주요 코드를 보자.

public static ArrayList<Integer> kmp(String str, String pattern) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		int[] pi = getPi(pattern);
		int n = str.length(), m = pattern.length(), j = 0;
		char[] s = str.toCharArray();
		char[] p = pattern.toCharArray();
                // str - 전체 문자열, pattern - 찾을 문자열
		// j - 찾을 문자열의 비교 인덱스.
		// i - 전체 문자열과 비교할 인덱스이기 때문에 1씩 증가하기만 함. 절대 불규칙적으로 변경되지 않음.

		for (int i = 0; i < n; i++) {
			while (j > 0 && s[i] != p[j]) {
				// 중간 단계 뛰어넘기.
				// pi배열을 이용하여 j인덱스를 변경시킴으로써 while문 중단.
				j = pi[j - 1];
			}
			
			if (s[i] == p[j]) {
				if (j == m - 1) {
					// j는 비교 인덱스로써, 인덱스가 찾을 문자열의 크기에 도달하면 문자열 찾음.
					list.add(i - m + 1);
					// 여러 개의 찾을 문자열이 있을 수 있기 때문.
					j = pi[j];
				} else {
					j++;
				}
			}
		}
		return list;
	}

위 코드에서는 한 부분만 이해한다면 크게 문제없다.

아래를 보자.

while (j > 0 && s[i] != p[j]) {
	// 중간 단계 뛰어넘기.
	// pi배열을 이용하여 j인덱스를 변경시킴으로써 while문 중단.
	j = pi[j - 1];	
}

중간 단계 부분을 뛰어넘는 부분이다.

i는 전체 문자열의 비교할 인덱스이고, j는 찾을 문자열의 인덱스인 점을 인지하고 있어야한다.

비교할 인덱스 i의 요소와 찾을 문자열 인덱스 j의 요소가 다르다면 pi배열에 들어있는 값을 이용하여 j를 변경시키는 것이다.

이렇게 pi배열을 통해 j를 변경시킴으로써 이전의 일치했던 정보들을 그대로 다시 활용할 수 있어 불필요한 단계를 넘길 수 있게 된다.

여기서 i 인덱스는 1씩 증가하는 전체 문자열의 인덱스일 뿐이고, j 인덱스가 계속해서 변경되는 찾을 문자열의 인덱스인 점을 생각하자.

i는 생각할 것이 없다. 

j가 어떻게 변해서 어떻게 활용되는지만 이해하면 된다.

kmp 함수의 원리를 그대로 이용하여 pi배열을 만들 수 있다.

PI배열을 만드는 소스로 보자.

public static int[] getPi(String pattern) {
		int m = pattern.length();
		int j = 0;
		char[] p = new char[m];
		int[] pi = new int[m];

		p = pattern.toCharArray();

		for (int i = 1; i < m; i++) {
			while (j > 0 && p[i] != p[j]) {
				j = pi[j - 1];
			}
			if (p[i] == p[j]) {
				pi[i] = ++j;
			}
		}

		return pi;
	}

kmp 함수를 이해한다면 pi배열을 만드는 부분도 이해할 수 있다.

여러번 반복해서 읽어보자.

본인이 참고한 링크이다.

http://bowbowbow.tistory.com/6#comment5168448

위의 링크를 참고하여 글을 다뤘다.

본인은 여러번 봐야 이해를 할 수 있었다. 

조금 더 쉽게 다룰려고 했으나, 잘 모르겠다.

KMP 관련 문제 소스 Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/kmp

백준 알고리즘 5525번 IOIOI

https://www.acmicpc.net/problem/5525

백준 알고리즘 10769번 행복한지 슬픈지

https://www.acmicpc.net/problem/10769

백준 알고리즘 1786번 찾기

https://www.acmicpc.net/problem/1786