문자열 검색

브루트 포스법

선형검색을 확장한 단순한 알고리즘으로, 문자열을 순서대로 한개씩 맞춰서 검색한 후 맞을 때가지 반복을 하는 방법.

static int bfMatch(String txt, String pat) {
		int pt = 0;			// txt 커서
		int pp = 0;			// pat 커서

		while( pt != txt.length() && pp != pat.length()) {
			if(txt.charAt(pt) == pat.charAt(pp)) {
				pt ++;
				pp ++;
			}else {
				pt = pt - pp+1;
				pp = 0;
			}
		}
		if(pp == pat.length()) {
			return pt - pp;		// 검색 성공
		}
		return -1;			// 검색 실패
	}

KMP 법

브루트 포스법에서 검사한 결과를 버리지 않고 이를 효과적으로 활용하는 알고리즘.

접두사와 접미사가 일치하는 최대 길이를 구해야하며 일치하는 경우에 한서는 점프를 수행해서 넘어갈 수 있음.

예시

긴글: ababacabacaabacaaba

찾을 문자열: abacaaba

위와 같이 서로 다른 문자가 발견되면 일치하는 접두사의 크기에 한해서만 부분 문자열의 인덱스를 이동시켜서 다시 탐색함.

다시 위와같이 하나씩 비교하며 접두사가 일치하는 가장 큰 길이만큼만 이동시켜서 반복하여 매칭을 진행.

static int kmpMatch(String txt, String pat){
		int pt =1;		// txt 커서
		int pp =0;		// pat 커서
		int [] skip = new int[pat.length()+1];	// 건너뛰기 표
		
		// 건너뛰기 표 만들기
		skip[pt] = 0;
		while(pt != pat.length()) {
			if(pat.charAt(pt) == pat.charAt(pp)) {
				skip[++pt] = ++pp;
			}else if(pp == 0) {
				skip[++pt] = pp;
			}else {
				pp = skip[pp];
			}
		}

		// 검색
		pt = pp = 0;
		while( pt != txt.length() && pp !=pat.length()) {
			if(txt.charAt(pt) == pat.charAt(pp)) {
				pt++;
				pp++;
			}else if(pp == 0) {
				pt++;
			}else {
				pp = skip[pp];
			}
		}
		if(pp == pat.length())
			return pt-pp;
		return -1;
	}

보이어 무어법

KMP보다 효율이 좋은 알고리즘으로 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정함.

불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것이 주 목표.

static int bmMatch(String txt, String pat) {
		int pt;
		int pp;
		int txtLen = txt.length();
		int patLen = pat.length();
		int[] skip = new int[Character.MAX_VALUE + 1];
		for (pt = 0; pt < Character.MAX_VALUE; pt++)
			skip[pt] = patLen;
		for (pt = 0; pt < patLen - 1; pt++)
			skip[pat.charAt(pt)] = patLen - pt - 1;

		while (pt < txtLen) {
			pp = patLen - 1;

			while (txt.charAt(pt) == pat.charAt(pp)) {
				if (pp == 0)
					return pt;
				pp -= 1;
				pt -= 1;
			}
			pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
		}
		return -1;

	}