[Java/알고리즘] 문자열 검색 알고리즘 - KMP
서론
알고리즘 문제를 풀면서 필요한 효율적인 문자열 검색 알고리즘에 대해서 공부해보고, 깊게 이해해보려고 한다.
일반적인 문자열 검색
일반적인 문자열 검색은 ‘Naïve String Search’라고 칭하는데, 아래 코드처럼 검색 대상과 대상 패턴을 두고 문자열의 인덱스 기반으로 (0부터 전체 길이 - 패턴의 길이까지) 패턴과 똑같은 지 대입하는 방식으로 찾는다.
이 방식은 최악의 경우 O(N*M)의 시간복잡도가 소요되기 때문에 효율적이지 못하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class PatternFinder {
public static void main(String[] args) {
String targetString = "hello hello hello hellgate";
String pattern = "hell";
findPattern(targetString, pattern);
}
public static void findPattern(String targetString, String pattern) {
int targetStringSize = targetString.length();
int patternSize = pattern.length();
boolean unmatchedFlag = true;
System.out.println("Begin to find pattern \"" + pattern + "\" at target string \"" + targetString + "\"");
for(int i=0;i<=targetStringSize - patternSize;i++){ //문자열의 인덱스 기반으로 0부터 전체 길이 - 패턴의 길이까지 패턴과 비교
int j = 0;
for(;j<patternSize;j++){
if(targetString.charAt(i + j) != pattern.charAt(j)){
break;
}
}
if(j == patternSize){
System.out.println("Pattern \"" + pattern + "\" matched at " + (i + 1) + " ~ " + (i + patternSize));
unmatchedFlag = false;
}
}
if(unmatchedFlag){
System.out.println("Pattern unmatched");
}
}
}
조금 더 효율적인 문자열 검색 알고리즘은 없을까?
KMP 알고리즘(Knuth–Morris–Pratt algorithm)이 문자열 검색 알고리즘 중 준비 과정을 선형으로 진행할 수 있고 실패 함수 배열 (혹은 LPS, pi 배열)로 O(패턴의 길이 M)의 메모리만 추가적으로 필요하기 때문에 공간적으로도 효율적이다.
KMP는 Knuth–Morris–Pratt 세 사람이 고안한 알고리즘이기 때문에 이름의 앞글자를 따서 지어졌고, 문자열의 길이 N, 패턴의 길이 M에서 O(N+M)의 시간복잡도로 대부분 언어 라이브러리의 문자열 검색 함수에 비해 효율적이다.
KMP 알고리즘
KMP 알고리즘의 핵심은 접두사(Prefix) 접미사(Suffix) 개념을 활용해서 “반복되는 연산을 얼마나 건너뛸 수 있는지”에 집중해서 효율성을 높이는 것이다.
1
2
String str = "ABCDABCEZ";
String pattern = "ABCDABA";
위 str문자열에서 pattern 을 찾는다고 할 때를 가정해본다.
| A | B | C | D | A | B | C | E | Z |
|---|---|---|---|---|---|---|---|---|
| A | B | C | D | A | B | A |
에서 “ABCDAB”까지는 같지만, 마지막 문자 “C”와 “A”가 다름을 알 수 있었다.
| A | B | C | D | A | B | C | E | Z |
|---|---|---|---|---|---|---|---|---|
| A | B | C | D | A | B | A |
여기에서 일반적인 brute-force라면 바로 다음 인덱스부터 패턴을 비교하겠지만, 앞에서는 “C”와 “A”가 다르다는 것과 별개로 “ABCDAB”가 같다는 점도 알 수 있다.
| A | B | C | D | A | B | C | E | Z |
|---|---|---|---|---|---|---|---|---|
| A | B | C | D | A | B | A |
지금까지 같은 문자열 “ABCDAB” 중 패턴 내 접두사와 접미사가 일치하면서 그 길이가 최대인 부분을 보면 “AB”다. 현재 패턴에서 접미사로 보고 있는 “AB” 부분을, 다시 탐색할 때에는 접두사로 바라보고 해당 부분부터 다시 시작하면서 검색한다.
| A | B | C | D | A | B | C | E | Z | |||
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | B | C | D | A | B | A |
패턴의 접미사 위치를 접두사 위치로 해서 다음 “AB”로 건너뛰면서 탐색한다면 효율적으로 탐색할 수 있다. 이 효율성에 을 위해 접두사, 접미사에 집중 해야한다.
KMP 알고리즘 내 LPS 배열
LPS는 Longest Prefix which is also Suffix의 줄임말이다. 접두사이면서 접미사인 기준 문자열과 같지 않으면서, 가장 긴 문자열의 길이 값을 나타낸다. 이 값은 위의 로직에서 본 것처럼 KMP 알고리즘 내에서 중요한 역할을 한다.
아래에 예시를 들면,
1
2
3
4
5
6
7
8
9
10
11
12
13
Input : s = “aabcdaabc”
Output : 4
설명 : 문자열 "aabc"는 s 문자열의 접두사이면서 접미사이고, 가장 긴 문자열의 길이는 4이다.
Input : s = “ababab”
Output : 4
설명 : 문자열 "abab"는 s 문자열의 접두사이면서 접미사이고, 가장 긴 문자열의 길이는 4이다. 여기에서 "ababab"는 기준 문자열과 같기 때문에 LPS가 될 수 없다.
Input : s = “aaaa”
Output : 3
설명 : 문자열 "aaa"는 s 문자열의 접두사이면서 접미사이고, 가장 긴 문자열의 길이는 3이다. 여기에서 "aaaa"는 기준 문자열과 같기 때문에 LPS가 될 수 없다.
문자열에서 LPS를 구하는 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LPS {
public static void main(String[] args) {
String s = "aabcdaabc";
int n = s.length();
int len = 0; //접두사의 길이를 포인터로 할당
int [] pi = new int[n]; //pi[i] = s.substring(0, i)의 LPS 값
for(int i=1;i<n;i++){
while(len > 0 && s.charAt(i) != s.charAt(len)){
len = pi[len - 1];
}
if(s.charAt(i) == s.charAt(len)){
len++;
pi[i] = len;
}
}
System.out.println(Arrays.toString(pi));
}
}
1
2
# 출력값
[0, 1, 0, 0, 0, 1, 2, 3, 4]
💡 코드 요약
pi[i]란?
s.substring(0, i) 구간에서접두사 == 접미사인 가장 긴 문자열의 길이를 저장한 배열이다. pi[i]는 문자열 s.substring(0, i)의 LPS 길이를 의미한다.len 포인터의 의미
현재까지 매칭된 접두사의 길이를 나타내며, s.charAt(i)와 비교할 s.charAt(len) 위치를 가리킨다.불일치 시 처리 (while)
문자가 일치하지 않으면len = pi[len - 1]로 돌아가서 다음 가능한 접두사 위치에서 다시 비교한다.일치 시 처리 (if)
문자가 일치하면len++;하고 pi[i]에 저장한다.
LPS 배열을 이용한 KMP 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//패턴에 맞는 횟수를 반환하는 kmp
public static int kmp(String origin, String pattern){
int [] pi = getPi(pattern);
int count = 0;
int index = 0;
for(int i=0;i<origin.length();i++) {
while (index > 0 && origin.charAt(i) != pattern.charAt(index)){
index = pi[index - 1];
}
if (origin.charAt(i) == pattern.charAt(index)) {
if (index == pattern.length() - 1) {
count++;
index = pi[index];
} else {
index++;
}
}
}
return count;
}
public static boolean kmp(String origin, String pattern){
int [] pi = getPi(pattern); // pattern의 LPS 배열
int index = 0; // pattern 내에서 현재 비교 중인 위치
for(int i=0;i<origin.length();i++){
while(index > 0 && origin.charAt(i) != pattern.charAt(index)){
index = pi[index - 1];
}
if(origin.charAt(i) == pattern.charAt(index)){
if(index == pattern.length() - 1){
return true;
}else{
index++;
}
}
}
return false;
}
아래 str과 pattern을 예시로 KMP 알고리즘 수행을 순서대로 보인다.
1
2
String str = "ABCDABCDABAZ";
String pattern = "ABCDABA";
패턴 문자열의 LPS (pi 배열)
| pattern | A | B | C | D | A | B | A |
|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| LPS | 0 | 0 | 0 | 0 | 1 | 2 | 1 |
KMP 코드 내 for 문의 i 별 흐름표
i (for 문 인덱스) | origin.charAt(i) | pattern.charAt(index) | origin.charAt(i) == pattern.charAt(index) | index 이동 연산 | 다음 index |
|---|---|---|---|---|---|
| 0 | a | a | ✅ | index++ | 1 |
| 1 | b | b | ✅ | index++ | 2 |
| 2 | c | c | ✅ | index++ | 3 |
| 3 | d | d | ✅ | index++ | 4 |
| 4 | a | a | ✅ | index++ | 5 |
| 5 | b | b | ✅ | index++ | 6 |
| 6 | c | a | ❌ | index = pi[5] = 2 (되돌아감) | 2 |
| 6 | c | c | ✅ | index++ | 3 |
| 7 | d | d | ✅ | index++ | 4 |
| 8 | a | a | ✅ | index++ | 5 |
| 9 | b | b | ✅ | index++ | 6 |
| 10 | a | a | ✅ | index == pattern.length() - 1 → return true | (종료) |
i기준 0~5까지 패턴 문자열과 일치하다가, 6번에서 문자열이 일치하지 않아서 인덱스를pi[index - 1]인 2로 되돌아간 후에 다시 6번 인덱스에 대한 일치 여부를 계속 판단해서 문자열을 찾을 수 있었다.
결론
알고리즘 문제 중에 문자열 검색 로직이 필요할 일이 많은데 String.contains() 메소드를 이용하면 시간 초과가 발생하는 경우가 더러 있었다. 이전 SSAFY 때부터 효율적인 문자열 검색 알고리즘으로 KMP를 배워왔지만 정리하면서 제대로 깊게 학습할 수 있었다. 다음으로는 Java의 String.contains()에 대해 조금 더 알아볼 예정이다.