문자열 패턴 매칭

Brute Force

: 문자열을 처음부터 끝까지 차례대로 검사

→ 시간복잡도 O(nm) (최악의 경우, 문자열 길이 * 패턴 길이)

• Java

public int BruteForce(String text, String pattern) {
	int N = text.length();
    int M = pattern.length();
    int i = 0;		// 검사 중인 문자열 인덱스
    int j = 0;		// 패턴 내 통과된 문자 수
    while(i < N) {
    	if(text.charAt(i) != pattern.charAt(j)) {
        	i -= j;		// 패턴과 일치한 만큼 뺀 인덱스
            j = -1;		// 패턴 첫글자부터 다시 검사
        }
        i++;
        j++;
    }
    if(j == M) {
    	return i - M;	// 패턴과 일치하는 부분 시작 인덱스 리턴
    } else {
    	return -1;
    }
}

• Python

def brute_force(text, pattern):
	N, M = len(text), len(pattern)
    i, j = 0, 0
    while i < N:
    	if text[i] != pattern[j]:
        	i -= j		# 패턴과 일치한 만큼 뺀 인덱스
            j = -1		# 패턴 첫글자부터 다시 검사
    	i += 1
        j += 1
        
	if j == M:
    	return i - M;	# 패턴과 일치하는 부분 시작 인덱스 리턴
	else:
    	return None

 

 

---

Boyer Moore

: 패턴 끝에서부터 검사하며, 일치하지 않는 문자가 나타나면 정해진 규칙에 따라 오른쪽으로 Skip해서 다시 검색 (문자열은 앞보다 뒤에서 불일치가 일어날 확률 높음)

→ 시간복잡도 O(n/m)

cf) 대부분의 상용 소프트웨어에서 사용

 

🪄 Skip table 작성

1. Bad Character Shift : 비교할 필요가 없는 문자들은 완전히 건너뛰도록 비교시작지점을 정함
   문자열에 패턴 문자가 없거나, 패턴의 마지막 문자라면 패턴 크기(M)만큼 Skip

2. Good Suffix Shift : 패턴에 들어있는 문자(단, 패턴 마지막 문자 제외)
   Skip 크기 = M - idxOfPattern - 1

   (실제 검색 시에는 해당 문자의 상대적 위치에 따라 Skip 크기가 결정됨
   → Skip table대로 문자열의 문자와 동일한 패턴 문자가 같은 위치에 오도록 패턴 이동
       or 해당 문자를 건너뛰도록 패턴 이동)

 

🔎 예시

원본 문자열 text = "BBACDZABACD"
검색 패턴 pattern = "ABACD" → 패턴 크기 M = 5

1. Skip table 작성

   문자	A	B	C	D	E	F	...
   아스키 코드 (인덱스)	65	66	67	68	69	70	...
   Skip 크기 (배열 값)	2	3	1	5	5	5	5

    

2. 패턴 끝에서부터 검색 시작 (텍스트커서 tc = 패턴커서 pc = M - 1 = 4)
   → 일치 시 커서를 한 칸씩 앞으로 이동하여 검색
   

3. 불일치 시 Skip
   : 텍스트커서 tc에 skip[text.charAt(tc)]와 (M - pc) 중 더 큰 값을 더함

   • skip[text.charAt(tc)] = skip[text,charAt(0)] = skip['B'] = skip[66] = 3
   • M - pc = 5 - 0 = 5
     

4. 패턴에 없는 문자의 경우, 패턴 크기만큼 Skip
   

5. 검색 성공 → return 6 (== tc)
   

Character는 0 ~ 65535 값을 가지므로 (상수 Character.MAX_VALUE = 65535)
char형으로 나타낼 수 있는 문자수는 총 (65535 + 1)개

 

💡 간략한 Boyer-Moore법

• Java

public int BoyerMoore(String text, String pattern) {
	int N = text.length();
    int M = pattern.length();
    int[] skip = new int[Character.MAX_VALUE + 1];
    
    // skip table 만들기
    int tc, pc;							// 텍스트 커서, 패턴 커서
    for(tc = 0; tc <= Character.MAX_VALUE; tc++) {
    	skip[tc] = M;
	}
    for(tc = 0; tc < M - 1; tc++) {		// 패턴에 들어있는 문자
    	skip[pattern.charAt(tc)] = M - tc - 1;
    }	// tc == M - 1
    
    // 검색
    while(tc < N) {
    	pc = M - 1;		// 패턴 끝에서부터 검색
        
        while(text.charAt(tc) == pattern.charAt(pc)) {	// 일치
        	if(pc == 0) {
            	return tc;	// 매칭 성공 (인덱스 리턴)
            }
            pc--;		// 앞으로 이동
            tc--;
        }
        // 불일치 시 스킵(큰 값만큼 텍스트 커서 이동)
        tc += (skip[text.charAt(tc)] > M - pc) ? 
        		skip[text.charAt(tc)]: M - pc;
    }
    
    return -1;			// 매칭 실패
}