문자열 패턴 매칭

문자열 패턴 매칭

• 패턴 매칭에 사용되는 알고리즘
• 고지식한 패턴 검색 알고리즘
• 라빈-카프 알고리즘
• 보이어-무어 알고리즘
• KMP 알고리즘

고지식한 패턴 매칭 알고리즘

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작

p[] : 찾을 패턴, t[] : 전체 텍스트
M : 찾을 패턴의 길이, N : 전체 텍스트의 길이

BruteForce(p[] , t[])
	i<- 0, j<-0
	WHILE j<M AND i<N
		IF t[i] != p[j]
			i<-i-j
			j<- -1;
		i <- i+1
		j <- j+1
	IF j == M : RETURN i - M
	ELSE	   : RETURN i

• 알고리즘의 시간 복잡도
  • 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야하므로 O(MN)이 됨.
  • 예에서는 최악의 경우 약 10000 * 80 = 800000번의 비교가 일어난다.

라빈-카프 알고리즘

• 문자열 검색을 위해 해시 값 함수를 이용
• 패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
• 최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘
• 패턴의 해쉬값을 계산한다.
  • 각 자리의 숫자에 자리값을 곱하여 더한다.
  • 즉 4 * 10^3 + 3 * 10 ^ 2 + 2 * 10 + 1 = 4321
  • 해쉬값은 “4321”라는 문자열이 아니라 정수값 4321이 된다.
  • 패턴 문자열의 해쉬값을 계산하고,
• 찾고자 하는 문자열에서 4자리씩 해쉬값을 계산한다.
• 찾고자 하는 문자열에서 해쉬값을 구할 때
  • 찾고자 하는 문자열에서 한 글자씩 이동하며 패턴 길이만큼 읽어서 해쉬 값을 계산하는 것이 아니라.
  • 새로 추가되는 문자와 그전에 읽었던 값을 이용하여 해쉬값을 구한다.
  • 즉, 아래 그림처럼 다음 해쉬값을 구할때 그전의 해쉬값을 이용한다.
  • 6842가 해쉬값이였을때, 다음 해쉬값은 6은 버리고 842 * 10 + 다음숫자를 해서 해쉬값을 구한다.
• 고려사항
  • 처음 해쉬 값을 구할 때는 찾고자하는 문자열에서 패턴 길이만큼 읽어서 구한다.
  • 본 예제에서는 이해를 돕기 위해 패턴의 길이를 4자리 정수로 작게 했지만 패턴이 문자열이며 길이가 커지면 길이를 일정 자리수로 맞추기 위해 mod 연산을 취해 준다.
  • 따라서 해쉬 값이 일치하더라도 실제 패턴이 일치하지 않을 수 있기 떄문에 해쉬 값이 일치하면 문자열 일치를 검사해야 한다.(이를 해쉬 충돌이라 한다.)

보이어 무어 알고리즘

• 오른쪽에서 왼쪽으로 비교
• 보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이 만큼이 된다.
• 최악의 시간 복잡도는 O(MN)이지만 최선의 시간복잡도는 O(N/M)이며 평균적으로 가장 빠른 속도를 가지는 알고리즘
• skip 배열 만들기
  • skip[ch] : 본문 ch 문자에서 패턴 불일치가 발생했을 때 본문포인터의 skip 횟수
  • 패턴에 포함되지 않은 문자들은 본문포인터가 패턴 길이만큼 skip 해야하므로 패턴의 길이가 skip 배열의 값이 됨.
  • 패턴 문자들의 skip 배열값(패턴 마지막 문자는 제외한다.)
  • (패턴문자열의 길이 -1)- 각패턴 문자의 인덱스
  • rithm패턴문자열의 skip 배열

KMP 알고리즘

• Knuth-Morris-Pratt Algorithm
• 불일치가 발생한 텍스트 문자열의 앞 부분에서 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
• 패턴을 전처리하여 부분일치 테이블 배열 pi[k]를 구해서 작못된 시작을 최소하함
  • pi[k] : 처음부터 k인덱스까지를 끝으로 하는 부분 문자열에서 일치하는 접두사와 접미사가 일치하는 최대 길이.
• 시간 복잡도 : O(M+N)
• 아이디어 설명
  • 텍스트에서 ABCDABC까지는 매치되고, E에서 실패한 상황 패턴의 맨 앞의 ABC와 실패 직전의 ABC는 동일함을 이용할 수 있다.
  • 실패한 텍스트 문자와 p[4]를 비교한다.
• 패턴을 이용하여 부분일치 테이블 배열 작성
• 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
• 패턴의 0번째 인덱스를 제외한 각 인덱스마다 맨 앞부터 해당 인덱스까지의 부분문자열 중 접두사와 접미사가 일치하는 최대 길이로 계산하여 작성.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

// KMP 알고리즘(Knuth–Morris–Pratt Algorithm)
// O(N+M)

public class String_KMPTest {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		char[] text = in.readLine().toCharArray();
		char[] pattern = in.readLine().toCharArray();

		int tLength = text.length, pLength = pattern.length;

		// 부분일치테이블 만들기 : KMP의 아이디어를 똑같이 적용, W에서 W를 찾는 듯한 행위를 해서...
		int[] pi = new int[pLength];
		//패턴포인터를 어디로 옮겨야하는지 인덱스저장
	    for(int i=1, j=0; i<pLength; i++){// i:접미사 포인터(i=1부터 시작: 우리는 실패함수를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.), j:접두사 포인터
	        while(j > 0 && pattern[i] != pattern[j]) {
	        	j = pi[j-1];
	        }
	        if(pattern[i] == pattern[j]) pi[i] = ++j;
	        else pi[i] = 0;
	    }

		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<Integer>();
		// i : 텍스트 포인터 , j: 패턴 포인터
		for(int i=0,j=0; i<tLength; ++i) {

			while(j>0 && text[i] != pattern[j]) j = pi[j-1];

			if(text[i] == pattern[j]) { //두 글자 일치
				if(j == pLength-1) { // j가 패턴의 마지막 인덱스라면
					cnt++; // 카운트 증가
					list.add((i+1)-pLength);
					j=pi[j];
				}else { //패턴 일치 중간 과정(패턴 앞쪽 일치하며 진행중인 상황)
					j++;
				}
			}
		}

		System.out.println(cnt);
		if(cnt>0) {
			System.out.println(list);
		}
	}
}