KMP 문자열 검색 알고리즘

Tushar Roy - Coding Made Simple님의 
Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) 영상을 정리했습니다.

 

KMP 하위 문자열 검색(KMP Substring Search)

문자열이 있을 때, 패턴 문자열이 문자열 안에 존재하는지 여부를 판단하는 알고리즘

 

문자열 abcbcglx에 패턴 bcgl이 존재하는지의 여부를 확인할 때, 일반적인 방법은 반복문을 돌리면서 문자열을 하나씩 비교하는 것이다. 이 경우 시간복잡도는 문자열의 길이 M, 패턴 길이 N에 비례하는 O(MN)이다.

 

KMP 검색은 O(M+N) 시간에 하위 문자열 검색을 수행할 수 있다.

 

 

알고리즘

문자열 abxabcabcaby에서 패턴 abcaby이 존재하는지 KMP 알고리즘을 통해 구해본다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

문자열의 처음과 패턴의 처음을 일치시키면서 비교한다. 처음 ab는 일치하지만 x와 c는 불일치한다.

이 때 비교를 마친 패턴의 문자열 중, 접두사이자 접미사인 문자열이 있는지 확인한다. 

ab에는 그러한 문자열이 존재하지 않기 때문에 x와 패턴의 처음부터 다시 비교한다.

 

여기서 접두사이자 접미사인 문자열이 존재한다는 것은 비교를 마친 패턴의 문자열 중에서 0번째부터 K번째까지의 문자와, N-K-1번째부터 N-1번째까지의 문자가 일치하는 것이다. (N은 패턴 문자열의 길이)
예를 들어 abc는 3개가 전부 다른 문자이므로 존재하지 않는다.
abcabc의 경우 앞의 3개의 문자(0번째부터 2번째까지의 문자) abc와 뒤의 3개의 문자(3번째부터 5번째까지의 문자) abc가 일치한다.  
baab의 경우 앞의 1개의 문자 b와 뒤의 1개의 문자 b가 일치한다. 이런 경우를 접두사이자 접미사인 문자열이 존재한다고 한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

x와 a는 일치하지 않기 때문에 다음 문자열과 비교한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

c와 y가 불일치한다. 

비교를 마친 패턴의 문자열 중, 접두사이자 접미사인 문자열이 있는지 확인한다. 

abcab에서 접두사 ab와 접미사 ab는 일치한다. y의 앞인 abcab 까지는 문자열이 일치했기 때문에, y의 앞의 비교한 두개의 문자는 ab이다. ab를 다시 비교할 필요가 없으므로, 문자열의 다음 비교는 접두어 ab의 다음인 c부터 시작한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

c부터 패턴의 마지막 글자인 y까지 일치하므로 문자열 안에 패턴이 존재한다.

 

위의 과정에서 접두사와 접미사가 일치하는지를 효율적으로 확인하기 위해 배열을 사용한다.

 

 

pi 배열을 구하는 방법 

 

패턴 abcdabca의 pi 배열을 구해볼 것이다.

 

	i,j
패턴	a	b	c	d	a	b	c	a
pi	0

 

pi[0] = 0으로 시작한다.

 

	i	j
패턴	a	b	c	d	a	b	c	a
pi	0	0

 

0번째 문자 a와 1번째 문자 b가 일치하지 않으므로 pi[1] = 0이고 j의 값을 1 증가시킨다.

 

	i		j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0

 

0번째 문자 a와 2번째 문자 c가 일치하지 않으므로 pi[2] = 0이고 j의 값을 1 증가시킨다.

 

	i			j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0

 

0번째 문자 a와 3번째 문자 d가 일치하지 않으므로 pi[3] = 0이고 j의 값을 1 증가시킨다.

 

	i				j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0	1

 

0번째 문자 a와 4번째 문자 a가 일치하므로 p[4] = 0+1 (i+1) 해서 1이 된다. i와 j를 동시에 증가시킨다.

위의 pi[4]=1이라는 뜻은, 길이가 1인 접두사와 접미사가 같은 문자열이 있다는 것을 의미한다.

 

		i				j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0	1	2

 

1번째 문자 b와 5번째 문자 b가 일치하므로 p[5] = 1+1 (i+1) 해서 2가 된다. i와 j를 동시에 증가시킨다.

위의 pi[5]=2라는 뜻은, 길이가 2인 접두사와 접미사가 같은 문자열이 있다는 것을 의미한다.

 

			i				j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0	1	2	3

 

2번째 문자 c와 6번째 문자 c가 일치하므로 p[6] = 2+1 (i+1) 해서 3이 된다. i와 j를 동시에 증가시킨다.

위의 pi[6]=3라는 뜻은, 길이가 3인 접두사와 접미사가 같은 문자열이 있다는 것을 의미한다.

 

				i				j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0	1	2	3

 

불일치하므로 i는 이전 문자의 값인 (c 지점의 pi값, pi[2]) 0 지점으로 이동한다. 

 

	i							j
패턴	a	b	c	d	a	b	c	a
pi	0	0	0	0	1	2	3	1

 

0번째 문자 a와 7번째 문자 a가 일치하므로 p[6] = 0+1 (i+1) 해서 1이 된다.

이것은 임시배열이며 이 배열은 하위 문자열 검색을 효율으로 수행하는데 도움이 된다.

배열을 구축하는데 걸리는 시간 복잡도는 O(N)이고, 공간복잡도도 O(N)이다.

 

 

pi 배열을 사용한 KMP 알고리즘

 

문자열 abxabcabcaby에서 패턴 abcaby이 존재하는지 KMP 알고리즘을 통해 구해본다.

 

인덱스	0	1	2	3	4	5
패턴	a	b	c	a	b	y
pi	0	0	0	1	2	0

 

패턴 abcaby의 pi 배열은 위와 같다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

2번째 문자에서 일치하지 않는다. 문자열을 다시 보지 않을 것이기 때문에 c의 앞의 패턴인 b의 pi 배열값을 확인한다.

pi[1] = 0이므로 다음 비교 지점은 x(문자열의 2번째)와 a(패턴의 0번째)가 된다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

x와 a는 불일치 하므로 문자열의 3번째 문자로 이동한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

c와 y가 불일치한다. 패턴에서 y의 앞의 값인 b의 배열값 p[4] = 2이고, 이는 길이가 2인 접두사가 있다는 뜻이다. 따라서 다음 비교 지점은 패턴의 2번째 문자가 된다. (앞에서부터 3번째 문자) . 따라서 c와(문자열의 8번째) 패턴의 c(패턴의 2번째)를 비교한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

문자열

a

b

x

a

b

c

a

b

c

a

b

y

패턴

a

b

c

a

b

y

 

c부터 패턴의 마지막 글자인 y까지 일치하므로 문자열 안에 패턴이 존재한다.

 

 

알고리즘의 실행시간 복잡도는 O(M)이고 M은 문자열의 길이이다.

배열을 구축하는 시간은 O(N)이기때문에 알고리즘의 총 시간은 O(M+N)이고 공간복잡도는 O(N)이 된다.

 

 

구현 코드 (JAVA) 

 

출처 : Mission Peace

https://github.com/mission-peace/interview/blob/master/src/com/interview/string/SubstringSearch.java

GitHub - mission-peace/interview: Interview questions

 

 

직접 구현한 코드

(백준 1786번 찾기)

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ1786 {
    static int[] pi;
    static int count;
    static StringBuilder sb = new StringBuilder();
    private static void makePi(String pattern) {
        pi = new int[pattern.length()];
        int i = 0;
        int j = 1;
        pi[0] = 0;
        while (j < pattern.length()) {
            if (pattern.charAt(i) != pattern.charAt(j)) {
                if (i == 0) {
                    pi[j] = 0;
                    j++;
                } else {
                    i = pi[i - 1];
                }
            } else {
                pi[j] = i + 1;
                i++;
                j++;
            }
        }
    }

    public static void kmpSearch(String str, String pattern) {
        makePi(pattern);
        int i = 0;
        int j = 0;
        while(i <= str.length()) {
            if (j == pattern.length()){
                count++;
                sb.append(i-j+1).append(" ");
                j = pi[j - 1];
            }
            if (i == str.length())
                break;
            if (str.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
            } else {
                if (j == 0){
                    i++;
                    continue;
                }
                j = pi[j-1];
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        kmpSearch(br.readLine(), br.readLine());
        System.out.println(count);
        System.out.println(sb);
    }
}