[자료구조] Java 문자열 검색

문자열 검색이란?

어떤 문자열 안에 다른 문자열이 들어있는지 조사하고, 위치를 찾아내는 것

T(본문), P(패턴) 

T : ABABAAABBAB, P : BAA 라고 할때 3~5번요소를 찾는 것.

대표적으로 브루트-포스법, KMP, Boyer-Moore 3가지 방법이 있다.

 

브루트-포스법(Brute Force)

해석하면 무식한 힘이란 뜻으로 단순한 방법으로 모든 경우의 수를 시험해보는 방법이다.

본문에서 패턴의 문자를 하나씩 왼쪽에서 오른쪽으로 이동하며 비교한다.

1. 다른 문자를 만나면 패턴에서 문자를 검사했던 결과 초기화.

2. 다음 텍스트의 위치로 1칸 이동.

3. 다시 패턴의 첫 번째 문자부터 검사.

시간 복잡도는 본문 길이N, 패턴길이 M 이라고 할때, O(NM)이다.

효율이 좋지 않으며, 메서드는 아래 코드와 같다.

 

int bruteForce(String txt, String pat) {
	int txtPoint = 0; // 본문 위치
	int patPoint = 0; // 패턴 위치
		
	while(txtPoint < txt.length() && patPoint < pat.length()) {
		if(txt.charAt(txtPoint) == pat.charAt(patPoint)) {
			txtPoint++;
			patPoint++;
		} else {
			txtPoint = txtPoint - patPoint + 1;
			patPoint = 0;
		}
	}
		
    //검색 성공 시 패턴의 시작위치 반환
	if(patPoint == pat.length()) return txtPoint - patPoint; 
	
    //검색 실패시 -1 반환
    return -1; 
}

 

KMP법

D.E. Knuth, J.H. Morris, V.R.Pratt가 거의 같은 시기에 고안했기 때문에

이들 이름의 각 앞글자를 따서 KMP 알고리즘이라 부른다.

브루트 포스법과는 다르게 패턴의 위치 결과를 버리지 않고 이를 효율적으로 활용한다.

비교할 필요가 없으면 패스하고, 비교할 필요가 있으면 비교하는 방법이다.

시간복잡도는 본문길이 N, 패턴길이 M이라고 할때, O(N+M)이다. 

 

int kmp(String txt, String pat) {
	int txtPoint = 1; // 본문 위치 
	int patPoint = 0; // 패턴 위치
    int[] skip = new int[pat.length() + 1];
		
	//건너 뛰기 표 만들기
	skip[txtPoint] = 0;
	while(txtPoint != pat.length()) {
		if(pat.charAt(txtPoint) == pat.charAt(patPoint)) {
			skip[++txtPoint] = ++patPoint;
		} else if(patPoint == 0) {
			skip[++txtPoint] = patPoint;
		} else {
			patPoint = skip[patPoint];
		}
	}
		
	//검색 
	txtPoint = patPoint = 0;
	while(txtPoint != txt.length() && patPoint != pat.length()) {
		if(txt.charAt(txtPoint) == pat.charAt(patPoint)) {
			txtPoint++;
			patPoint++;
		} else if(patPoint == 0) {
			txtPoint++;
		} else {
			patPoint = skip[patPoint];
		}
	}
	
	if(patPoint == pat.length()) return txtPoint - patPoint;
	return -1;
	 
}

+추가적인 설명 :ee-22-joo.tistory.com/8

문자열 검색 알고리즘 개념 (브루트포스, KMP, Boyer-Moore)

 

Boyer-Moore법

R.S Boyer와 J.S Moore가 만들었다.

기존 검색 방법들과 다르게 오른쪽에서 왼쪽으로 문자열을 비교한다.

하지만 이동 할 때는 왼쪽에서 오른쪽으로 하며, 최대한 많이 건너 뛰며 비교한다.

크게 Bac Character Rule(문자값 이용), Good Suffix Rule(문자열 이용)두 가지 방식의 탐지 방식을 이용하며,

두 가지 방식 중 더 큰 값만큼 이동하는 방식을 선택하여 패턴 매칭을 시도하게 된다.

코드는 아래와 같다.

static int bmMatch(String txt, String pat) {
	int txtPoint;
	int patPoint;
	int txtLen = txt.length();
	int patLen = pat.length();
	int[] skip = new int[Character.MAX_VALUE + 1];
	
	//건너뛰기 표 만들기
	//Character.MAX_VALUE는 char형으로 나타낼 수 있는 문자수
	for(txtPoint = 0; txtPoint <= Character.MAX_VALUE; txtPoint++) 
		skip[txtPoint] = patLen;
	for(txtPoint = 0; txtPoint < patLen-1; txtPoint++) 
		skip[pat.charAt(txtPoint)] = patLen - txtPoint - 1;
	
	//검색 
	while(txtPoint < txtLen) {
		patPoint = patLen - 1; //마지막 문자부터 비교 
		
		while(txt.charAt(txtPoint) == pat.charAt(patPoint)) {
			if(patPoint == 0) return txtPoint; //pattern의 문자열 크기가 1인 경우 검색 성공 
			patPoint--;
			txtPoint--;
		}
		
		txtPoint += (skip[txt.charAt(txtPoint)] > patLen - patPoint)? 
				skip[txt.charAt(txtPoint)] : patLen - patPoint;
	}		
	return -1;
}

 

요약

	브루트 포스	KMP	Boyer_Moore
비교기준	문자값	문자열	문자값 & 문자열 혼합 사용
비교검사 방향	->	->	<-
이동간격	한칸	패턴(P) 글자수 이내	패턴(P) 글자수 이내
이동경로 저장여부	X	O	O
시간복잡도	O(NM)	O(N+M)	최상 : O(N+M/M) 최악 : O(NM)

 

 

+ 코드 출처: sustainable-dev.tistory.com/53