오늘은 문자열을 검색하는 알고리즘 중에 문자열 검색의 기초라고 할 수 있는 브루트-포스법에 대해 알아보자.
📘 문자열 검색
문자열을 검색하는 알고리즘에 대해 알아보자.
문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말한다.
예를 들어 문자열 "STRING" 에서 "IN"을 검색하면 문자열 검색에 성공한다. 하지만 "QUEEN"에서 "IN"을 검색하면 문자열 검색에 실패한다.
여기서는 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하겠다.
📘 브루트-포스법
📜 브루트-포스법의 원리
다음의 그림은 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트-포스법(brute force method)을 사용해 검색하는 순서를 간략하게 나타낸 그림이다.
✏ 🅐
텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사한다.
'A'와 'B'는 일치하고 'C'는 다르다.
✏ 🅑
패턴을 1칸 뒤로 옮긴다.
텍스트의 2번째 문자부터 3개의 문자가 일치하는지 조사한다.
'A'와 'B'가 다르다.
✏ 🅒
패턴을 다시 1칸 뒤로 옮긴다.
'A', 'B', 'C' 모두 일치한다.
브루트-포스법은 선형 검색을 확장한 알고리즘이므로 단순법(單純法), 소박법(素朴法)이라고도 한다.
📜 브루트-포스법 코드
브루트-포스법으로 문자열을 검색하는 프로그램을 살펴보자.
import java.util.Scanner;
// 브루트-포스법으로 문자열을 검색하는 프로그램
public class BFmatch {
// 브루트-포스법으로 문자열을 검색하는 메서드
static int bfMatch(String text, String pattern) {
int pt = 0; // text 커서
int pp = 0; // pattern 커서
while (pt != text.length() && pp != pattern.length()) {
if (text.charAt(pt) == pattern.charAt(pp)) {
pt++;
pp++;
} else {
pt = pt - pp + 1;
pp = 0;
}
}
if (pp == pattern.length()) // 검색 성공
return pt - pp;
return -1; // 검색 실패
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("원본 텍스트 : ");
String text = sc.nextLine(); // 텍스트용 문자열
System.out.print("검색할 패턴 : ");
String pattern = sc.nextLine(); // 패턴용 문자열
int idx = bfMatch(text, pattern); // 문자열 text에서 문자열 pattern을 검색
if (idx == -1) System.out.println("텍스트에 패턴이 없습니다.");
else { // 일치하는 문자 바로 앞까지의 길이 구하기
int len = 0;
for (int i = 0; i < idx; i++)
len += text.substring(i, i + 1).getBytes().length;
len += pattern.length();
System.out.println((idx + 1) + "번째 문자부터 일치");
System.out.println("텍스트 : " + text);
System.out.printf(String.format("패턴 : %%%ds\n", len), pattern);
}
}
}bfMatch 메서드
텍스트(text)에서 패턴(pattern)을 검색하여 텍스트의 위치(인덱스)를 반환한다.
텍스트에 패턴이 여러 개 있는 경우 가장 앞쪽에 위치한 텍스트의 인덱스를 반환하고 검색에 실패하면 -1을 반환한다.
텍스트(text)를 스캔하기 위한 변수로 pt를 사용하고, 패턴(pattern)을 스캔하기 위한 변수로 pp를 사용한다.
두 변수는 처음에는 0으로 초기화하고 스캔을 하거나 패턴을 옮길 때마다 업데이트한다.
main 메서드
메인 메서드에서 사용된 for문에서 substring 메서드로 텍스트 문자열의 각각의 문자를 처리하고 그 다음 getBytes 메서드로 바이트(byte) 배열로 반환한다.
==> String. getBytes 메서드는 문자열을 바이트 순서(byte sequence)대로 부호화하여 바이트 배열에 넣어두는 메서드이다.
(부호화할 때는 플랫폼의 기본 문자 세트(default chatater set)를 사용한다.)
📜 추가 자료 - String.indexOf 메서드로 문자열 검색하기
java.lang.String 클래스는 문자열을 검색하는 indexOf 메서드와 lastIndexOf 메서드를 제공한다.
1) int indexOf(String str)
2) int indexOf(String str, int fromIndex)
3) int laseIndexOf(String str)
4) int lastIndexOf(String str, int fromIndex)위의 메서드는 모두 지정한 문자열(str)이 포함되어 있는지 검색한다.
1번과 3번은 모든 문자열에 대해 검색을 하고, 2번과 4번은 fromIndex부터의 문자열에 대해서 검색한다.
이때 3, 4번은 같은 문자열에 대해서 가장 마지막 위치의 문자열을 검색한다.
검색에 성공하면 찾은 문자열(텍스트)의 인덱스를 반환하고 실패하면 -1을 반환한다.
✏ String.indexOf를 이용한 코드
위의 브루트-포스법의 코드를 String.indexOf 메서드를 이용한 코드로 수정해보자.
import java.util.Scanner;
// String.indexOf, String.lastIndexOf 메서드로 문자열을 검색
public class BFmatch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("원본 텍스트 : ");
String text = sc.nextLine(); // 텍스트용 문자열
System.out.print("검색할 패턴 : ");
String pattern = sc.nextLine(); // 패턴용 문자열
int idx1 = text.indexOf(pattern); // 문자열 text에서 pattern을 검색
int idx2 = text.lastIndexOf(pattern);// 문자열 text에서 pattern을 검색
if (idx1 == -1) System.out.println("텍스트에 패턴이 없습니다.");
else {
// 찾아낸 문자열의 바로 앞까지의 문자 개수 구하기
int len1 = 0;
for (int i = 0; i < idx1; i++)
len1 += text.substring(i, i + 1).getBytes().length;
len1 += pattern.length();
int len2 = 0;
for (int i = 0; i < idx2; i++)
len2 += text.substring(i, i + 1).getBytes().length;
len2 += pattern.length();
System.out.println("텍스트 : " + text);
System.out.printf(String.format("패턴 : %%%ds\n", len1), pattern);
System.out.println("텍스트 : " + text);
System.out.printf(String.format("패턴 : %%%ds\n", len2), pattern);
}
}
}위의 프로그램을 실행하면 반각 문자는 1바이트의 바이트 배열로, 전각 문자는 3바이트의 바이트 배열로 바꾸어 출력한다. 따라서 바뀐 배열의 길이를 length 메서드를 사용하면 검색 대상의 문자가 1바이트인지 3바이트인지 알 수 있다.
이 값을 for문을 반복하여 누적한 다음 pattern의 길이를 더해 완성한다.
==> UTF-8 유니코드에선 영문/숫자/기호는 1바이트, 한글과 한자는 3바이트로 표현한다.
