[Java]KMP 문자열 탐색 알고리즘

KMP 알고리즘이란

이 알고리즘을 만든 Knuth, Morris, Prett 이렇게 3명의 앞 글자를 하나씩 따서 명명하여 KMP 알고리즘이라고 한다.

KMP 문자열 탐색 알고리즘의 시간 복잡도는 O(N+M)이다.(전체 문자열 길이 = N, 찾는 문자열 길이 = M)

LPS 배열 계산 O(M) + 매칭 O(N)

 

KMP 알고리즘의 핵심 아이디어

IDX

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Text

A

B

C

D

A

B

D

A

B

C

D

A

B

E

A

B

C

D

Pattern

A

B

C

D

A

B

E

위 표에서 text와 pattern 모두 0, 1번째 인덱스와 4, 5번째 인덱스의 값이 동일하다는 것을 알 수 있다.

즉, 앞에서 2개 뒤에서 2개가 같다는 것을 알 수 있다.

또한 6번째 인덱스부터 text와 pattern이 다르다는 것을 알 수 있다.

text와 pattern 모두 0, 1번째 인덱스와 4, 5번째 인덱스의 값이 동일하고, 6번째 인덱스부터 text와 pattern이 다르기 때문에, 다음 문자열 비교를 할 때, pattern의 첫 시작을 text와 pattern이 다른 곳(IDX 6)으로부터 앞에서 2번째인 인덱스 4부터 시작한다는 개념이다.

문자열이 불일치 할 때, 탐색을 시작했던 위치의 다음 문자 부터가 아닌 일정 부분을 건너 뛸 수 있다는 것이 핵심이다.

아래의 표를 보면 이해가 될 것이다. 

IDX

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Text

A

B

C

D

A

B

D

A

B

C

D

A

B

E

A

B

C

D

Pattern

A

B

C

D

A

B

E

여기서는 앞에서 몇개 뒤에서 몇개가 같은게 없다.

그리고 6번째 인덱스부터 text와 pattern이 다르다.

그러면 다음 문자열 비교를 할 때, pattern의 첫 시작을 text와 pattern이 다른 곳(IDX 6)부터 다시 비교를 하는 것이다.

IDX

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Text

A

B

C

D

A

B

D

A

B

C

D

A

B

E

A

B

C

D

Pattern

A

B

C

D

A

B

E

IDX 6부터 pattern의 길이(6)를 더한 IDX 12까지 일치하는 것이 없으므로 한 칸 옆으로 pattern을 이동시킨다.

IDX

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Text

A

B

C

D

A

B

D

A

B

C

D

A

B

E

A

B

C

D

Pattern

A

B

C

D

A

B

E

Text의 IDX7부터 찾는 문자열이 있음을 알 수 있다.

 

Prefix(접두사), Suffix(접미사), LPS배열

Prefix(접두사)와 Suffix(접미사)의 개념은 아래의 표를 보면 이해가 될 것이다.

BAABABAA 문자열에서 얻을 수 있는 접두사와 접미사는 아래와 같다.

BAABABAA
길이	접두사	접미사
1	B	A
2	BA	AA
3	BAA	BAA
4	BAAB	ABAA
5	BAABA	BABAA
6	BAABAB	ABABAA
7	BAABABA	AABABAA
8	BAABABAA	BAABABAA

 

LPS : Longest proper Prefix which is also Suffix

LPS의 길이를 담는 LPS 배열은 KMP 알고리즘에서 중요한 역할을 하는 배열이다.

Pattern "ABAABAB"에 대한 LPS 배열은 아래와 같다.

IDX	index까지의 패턴	LPS의 길이
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

 

위 표에서 IDX 3인 경우를 살펴보면

IDX	index까지의 패턴	LPS의 길이
3	ABAA	1

왜 LPS의 길이가 1인지는 아래와 같다.

길이	접두사	접미사
1	A	A
2	AB	AA
3	ABA	BAA

접두사와 접미사가 일치하는 최대 길이는 1이다

즉, 접두사와 접미사가 같을때, 그 최대 길이는 1이다.

이와 같이 접두사와 접미사가 같을 때, 그 최대 길이를 가지고 있는 배열이 바로 LPS배열이다.

 

LPS 배열이 의미하는 것

IDX	index까지의 패턴	LPS의 길이
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

IDX	index까지의 패턴	LPS의 길이
5	ABAABA	3

IDX	0	1	2	3	4	5	6	7	8
Text	A	B	A	A	B	A	Z
Pattern	A	B	A	A	B	A	B

전체 패턴 "ABAABAB" 중에서 일부인 "ABAABA" 까지 일치하고 그 다음 글자에서 불일치 했다면

다음 번 비교는 접두사가 다시 나타나는 IDX3 부터 시작하면 효율적이다.

즉, 틀린 위치인 IDX6에서 LPS의 길이인 3을 빼서 IDX3부터 다음 번 비교를 시작하면 되는 것이다.

 

이후 비교에서 IDX3부터 IDX5까지는 이미 일치하다는 것을 알고 있기 때문에, IDX6부터 비교를 하면 되는 것이다.

IDX	0	1	2	3	4	5	6	7	8
Text	A	B	A	A	B	A	Z	..	..
Pattern				A	B	A	A	B	A

 

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main
{
    static public ArrayList<Integer> KMP(String str, String pattern)
    {
        ArrayList<Integer> idxList = new ArrayList<>(); //찾는 문자열을 발견시 해당 문자열의 시작 인덱스를 저장하는 리스트
        int LPS[] = new int[pattern.length()]; //LPS 배열 생성
        int index = 0; //IDX, 찾을 문자열의 비교 인덱스를 뜻하기도 하며, 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 함
        for (int i = 1; i < pattern.length(); i++) //LPS배열의 값을 입력
        {
            if (pattern.charAt(i) == pattern.charAt(index)) LPS[i] = ++index; //접두사와 접미사가 같을 때, index를 1 증가
            else  //접두사와 접미사가 같지 않을 때
            {
                if (index != 0) //0이면 더 이상 돌아갈 위치가 없음
                {
                    index = LPS[index - 1]; //LPS[index - 1] : 이전 위치로 돌아가야 할 위치를 나타냄, 이 위치에서부터 비교를 다시 시작하여 일치하는 부분을 찾음
                    --i; // 현재 위치에서부터 다시 패턴 매칭을 시도(여기서 --i하고 이후 루프에서 ++i가 될테니)
                }
            }
        }
        index = 0; //0으로 초기화
        for(int i = 0; i < str.length(); i++) //문자열 탐색 시작
        {
            while(index > 0 && str.charAt(i) != pattern.charAt(index)) index = LPS[index - 1]; //LPS[index - 1] : 이전으로 돌아가야할 위치
            if(str.charAt(i) == pattern.charAt(index)) //접두사와 접미사가 같을 때
            {
                if(index == pattern.length() - 1) //IDX는 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 하는데, 이것이 pattern의 길이와 같다면 탐색 성공
                {
                    idxList.add(i - (index - 1)); //일치하는 첫 번째 인덱스를 추가
                    index = LPS[index]; //LPS[index] : 현재 일치하는 부분의 최대 길이를 나타내며, 이 길이만큼은 이미 패턴과 일치함이 보장
                }
                else ++index; //길이가 같지 않다면 index를 1증가
            }
        }
        return idxList;
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String pattern = br.readLine();
        ArrayList<Integer> list = KMP(str, pattern); //시작 인덱스들을 받아옴
        System.out.println(list.size() + "개 발견");
        System.out.print("인덱스 : ");
        for (Integer i : list) System.out.print(i + " "); //시작 인덱스들을 출력
    }
}