문자열 패턴 매칭

여러 알고리즘이 있지만, 아래 세가지에 대해서 정리할 계획입니다.

• Brute Force
• KMP
• 라빈-카프

Brute Force

이름 그대로 고지식하게 본문 문자열 처음부터 끝까지 차례대로 순회합니다. 일일이 다 비교하면서 동작합니다. 정말 하나하나 비교하므로 특별한 설명을 첨부하지는 않겠습니다.

시간 복잡도

문자열 각각의 길이를 M, N이라 할 때, 시간복잡도는 O(MN)입니다.

KMP

• Knuth-Morris-Pratt Algorithm
• Brute Force를 생각해보면 패턴이 틀린 것을 확인 할 경우 문자 하나하나를 비교하기 위해 처음부터 되돌아가서 비교를 하는 비효율성이 존재합니다.
• 불일치가 발생하면 문자열 앞 부분에 어떤 문자가 있는지 사실 우리는 이미 알고 있습니다
• 앞에 있는 건 다시 비교하지 말고 그냥 넘기자!
• 시간복잡도 : O(M + N)

부분 일치 테이블 배열(실패 함수)

• 패턴을 전 처리하여 부분 일치 테이블 배열(실패 함수)를 구해서 잘못된 시작을 최소화합니다.
  • 역할은 쉽게 생각해서 패턴 매칭 실패 했을 때, 얼만큼 건너 뛰어야 되는지를 알려줍니다.
  • 정확하게는 매칭에 실패하기 직전, 접두사 / 접미사가 일치한 최대 길이를 의미합니다.
• ABABACA에 대해서 이를 따져보면 다음과 같습니다.

i	부분 문자열	접두사면서 접미사인 최대 문자열	길이
0	A	-	0
1	AB	-	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABA	ABA	3
5	ABABAC	-	0
6	ABABACA	A	1

배열 구현 Java Code

public static int[] failureFunction(String pattern) {
	int size = pattern.length();
	int[] table = new int[size];
	int idx = 0; // 포인터 인덱스
	for(int i = 1; i < size; i++ ) { // i : 부분 문자열의 마지막 인덱스
        // i가 들어오면서 문자가 하나 추가 된 상황
		while(idx > 0 && pattern.charAt(idx) != pattern.charAt(i)) {
			idx = table[idx - 1];
		}
        // 현재 포인터가 새로 추가된 문자와 일치하면 접두사 길이 + 1
        // 포인터가 한칸 이동
		if(pattern.charAt(idx) == pattern.charAt(i)) {
			table[i] = ++idx;
		}
	}
	return table;
}

과정

"ABABACA"에 대해서 배열 만들기

A
idx = 0, i = 0, table[i] = 0

AB
idx = 0, i = 1, table[i] = 0

ABA
idx = 0, i = 2
idx = 1, table[i] = 1

ABAB
idx = 1, i = 3
idx = 2, table[i] = 2

ABABA
idx = 2, i = 4
idx = 3, table[i] = 3

ABABAC
idx = 3, i = 5
idx = 1, i = 5 // ABA에 C가 추가된다면?
idx = 0, i = 5, table[i] = 0

ABABACA
idx = 0, i = 6
idx = 1, table[i] = 1

전체 구현 코드

https://www.acmicpc.net/problem/1786
해당 문제의 소스코드이기도 합니다.

import java.io.*;

public class Main {
	static int count;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String t = br.readLine();
		String p = br.readLine();
		count = 0;
		sb = new StringBuilder();
		KMP(t, p);
		System.out.println(count);
		System.out.println(sb);
		br.close();
	}
	public static void KMP(String parent, String pattern) {
		int parentSize = parent.length();
		int patternSize = pattern.length();
		int[] table = failureFunction(pattern);
		int patternIdx = 0;
		for(int idx = 0; idx < parentSize; idx++) {
			while(patternIdx > 0 && parent.charAt(idx) != pattern.charAt(patternIdx)) {
				patternIdx = table[patternIdx - 1];
			}
			if(parent.charAt(idx) == pattern.charAt(patternIdx)) {
				if(patternIdx == patternSize - 1) {
					count++;
					sb.append(idx - patternSize + 2).append(" ");
					patternIdx = table[patternIdx]; // 테이블 반드시 확인
                    // abababab 에서 abab를 찾는 것을 생각해보자.
				} else {
					patternIdx++;
				}
			}
		}
	}
	public static int[] failureFunction(String pattern) {
		int size = pattern.length();
		int[] table = new int[size];
		int idx = 0;
		for(int i = 1; i < size; i++ ) {
			while(idx > 0 && pattern.charAt(idx) != pattern.charAt(i)) {
				idx = table[idx - 1];
			}
			if(pattern.charAt(idx) == pattern.charAt(i)) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}

라빈 카프

• 문자열 검색을 위해 해시 값 함수를 사용합니다.
• 최악의 경우 O(MN)이지만 평균적으로는 선형에 가까운 속도를 가지고 있습니다.
• 보통 해시를 만들 때는 곱해주는 상수로 31, 37과 같은 소수를 많이 사용합니다.

문자열 찾기

• 롤링해시를 사용 : 슬라이딩 윈도우
• 다음 문자열로 패턴이 넘어간다면
  - 맨 앞에 있는 문자를 버림 : 기존 해시에서 해당하는 문자에 해당되는 값을 빼주기
  - 기존 해시 * 상수 + 문자열에 해당하는 숫자
  • 앞 빼주고 뒤만 더해주는 슬라이딩 윈도우

주의점

• 처음 해시 값을 구할 때 찾고자 하는 문자열에서 패턴 길이 만큼 읽어서 구합니다
• 오버플로우를 주의해야됩니다. 해시를 구하고 모듈러 연산을 수행합니다.
• 해시 값이 일치해도 실제 패턴이 일치하지 않을 수 있습니다. 해시 충돌이라고도 하는데, 이 경우 검사가 필요합니다.
• 보통 해시를 여러개 두고 이 여러개의 해시가 서로 일치하는지 확인하는 방법으로 PS가 들어갑니다.