[Algorithm] KMP

String Mapping

문자열1 "ABCABABABDA"와 문자열2 "ABABDA"가 있을 때 문자열2가 문자열1의 부분 문자열임을 어떻게 알 수 있을까?

먼저 완전탐색으로 찾는 방법을 살펴보자.

str1의 인덱스 부터 차례대로 str2와 매핑되는 지 여부를 찾는 방법이 있다.

-	0	1	1	3	4	5	6	7	8	9	10
str1	A	B	C	A	B	A	B	A	B	D	A
str2	A	B	A	B	D	A	-	-	-	-	-

다음 인덱스로 넘어가서 비교하고, 이 과정을 반복한다.

-	0	1	1	3	4	5	6	7	8	9	10
str1	A	B	C	A	B	A	B	A	B	D	A
str2	-	A	B	A	B	D	A	-	-	-	-

...

-	0	1	1	3	4	5	6	7	8	9	10
str1	A	B	C	A	B	A	B	A	B	D	A
str2	-	-	-	-	-	A	B	A	B	D	A

6번째 인덱스에서 같아지므로 문자열2가 문자열1의 부분문자열임을 확인할 수 잇고,

O(N*M)의 시간 복잡도를 가진다. (N: 문자열1의 길이, M: 문자열2의 길이)

하지만 O(N*M)보다 더 줄일 수 있는 방법이 있다.
이 글에는 O(N)만큼 줄일 수 있는 KMP알고리즘을 설명하고자 한다.

LPS

KMP알고리즘을 살펴보기 전에 LPS(Longest Prefix Suffix)를 살펴보자.

접두사(Prefix): 문자열의 처음부터 시작하여 연속된 일부 문자.
접미사(Suffix): 문자열의 끝에서부터 시작하여 연속된 일부 문자.

LPS는 패턴 내에서 접두사와 접미사가 일치하는 가장 긴 길이를 의미한다.

-	0	1	2	3	4	5
str2	A	B	A	B	D	A
LPS	0	0	1	2	0	1

LPS 값은 문자열의 특정 위치까지의 접두사와 접미사가 일치하는 최대 길이를 나타낸다.
즉, LPS[3] = 2라는 뜻은 해당 위치에서 문자열의 처음부터 시작하는 접두사 2글자와 끝에서 시작하는 접미사 2글자가 일치한다는 의미이다.

코드를 살펴보자

public int[] makeLPS(String str2) {
    int M = str2.length();
    int[] LPS = new int[M];

    int j = 0;
    for(int i=1;i<M;i++) {
    	while(j>=0&&str2,charAt(i)!=str2,charAt(j)) {
    		j = LPS[j-1];
    	}
    	if(str2.charAt(i)==str2.charAt(j)) {
    		LPS[i] = ++j;
    	}
    }
    return LPS;
}

LPS[0]의 값은 0으로 고정이므로 LPS를 만들어야 하므로 i는 1부터 시작한다.

-	j=0	i=1	2	3	4	5
str2	A	B	A	B	D	A
LPS	0	-	-	-	-	-

str2[i]와 str2[j]가 같지 않으므로 i만 1증가시킨다.

-	j=0	1	i=2	3	4	5
str2	A	B	A	B	D	A
LPS	0	0	-	-	-	-

str2[i]와 str2[j]가 같으므로 i와 j를 1증가시키고 lps[i] 값은 j가 된다.

-	0	j=1	2	i=3	4	5
str2	A	B	A	B	D	A
LPS	0	0	1	-	-	-

str2[i]와 str2[j]가 같으므로 i와 j를 1증가시키고 lps[i] 값은 j가 된다.

-	0	1	j=2	3	i=4	5
str2	A	B	A	B	D	A
LPS	0	0	1	2	-	-

str2[i]와 str2[j]가 같지 않으므로, lps[j-1] = 0이므로 j = 0이 되고, lps[i] = 0이 된다.

여기서 j = lps[j-1]를 찾는 과정을 하는 이유는 이미 확인된 접두사/접미사 정보를 활용하여 불필요한 비교를 줄이기 위해서다.

-	j=0	1	2	3	4	i=5
str2	A	B	A	B	D	A
LPS	0	0	1	2	0	-

str2[i]와 str2[j]가 같으므로 lps[i] = j이 된다.

-	0	j=1	2	3	4	5
str2	A	B	A	B	D	A
LPS	0	0	1	2	0	1

KMP

KMP알고리즘에서 문자열의 접미사가 접두사와 일치하면 그 부분은 매핑할 필요가 없다. 그래서 LPS를 구한것이다.

public void KMP(String str1, String str2) {
    int N = str1.length();
    int M = str2.length();
    int[] LPS = makeLPS(str2);
    	
    int j = 0;
    for(int i=0;i<N;i++) {
    	while(j>=0&&str1,charAt(i)!=str2,charAt(j)) {
    		j = LPS[j-1];
    	}
    	if(str1.charAt(i)==str2.charAt(j)) {
    		j++;
    		if(j==str2.length()-1) {
    			j = LPS[j-1];
    			System.out.println("부분문자열 일치);
    		}
    	}
    }
}

KMP 알고리즘의 동작 과정

1. LPS 테이블 생성:

   • 먼저 패턴 문자열의 LPS 테이블을 생성한다. 이 과정은 이전에 설명된 방식으로 진행된다.

2. 텍스트와 패턴 비교:

   • 텍스트(str1)와 패턴(str2)을 순회하며 일치 여부를 확인한다.
   • 비교가 불일치하면 LPS 테이블을 참고하여 j 값을 조정해 비교를 이어간다.

3. 패턴 발견:

   • 패턴의 모든 문자가 일치하면(j == 패턴 길이), 패턴이 발견된 것이다.
   • 이후 LPS 값을 활용해 다음 비교를 이어간다.

시간 복잡도가 O(N)인 이유

1. 텍스트 순회

   • 텍스트 문자열 str1의 모든 문자(길이 N)를 최대 한 번만 순회한다.
   • 이 과정에서 비교가 이루어지며, 불일치가 발생하더라도 LPS 테이블을 활용해 i(텍스트 인덱스)는 절대로 뒤로 돌아가지 않는다.

2. 패턴 순회

   • 패턴 문자열 str2의 각 문자(길이 M)를 LPS 테이블 생성 시 최대 한 번 순회한다.
   • LPS 테이블 생성 자체의 시간 복잡도는 O(M)이다.

3. LPS 테이블 활용

   • 불일치 시 LPS 테이블 값을 이용해 패턴의 비교 위치(j)를 점프한다.
   • 점프는 이미 계산된 LPS 정보를 사용하므로 추가적인 비교가 필요하지 않는다.

O(N) = LPS를 만드는 시간 O(M) + 순회 시간 O(N)