문자열 검색이란
문자열 검색이란?? 어떤 문자열 안에 특정 문자열이 들어 있는지 조사하고, 들어 있다면 그 위치를 것을 말한다.
예를 들어 "STRING"이란 문자열에서 "IN"을 검색하면 검색에 성공하고, "ER"을 검색하면 검색에 실패하게 된다. 이 때, "IN", "ER"처럼 검색할 문자열을 '패턴(pattern)'이라 하고 문자열 원본을 '텍스트(text)'라고 한다.
참고로 자바에서 String클래스는 기본형 자료형이 아닌 참조형으로, byte형 배열 value를 가지는 클래스이다. 해당 value배열을 활용할 수 있는 여러 메서드들도 같이 존재한다.
public final class String implements ... {
@Stable
private final byte[] value;
...
}브루트-포스법이란?
브루트-포스는 다양한 분야에서 사용되는 방식으로
브루트-포스법의 시간 복잡도
이 알고리즘의 시간 복잡도는 O(mn)이지만, 일부러 만든 패턴이 아닌 한 실질적인 시간 복잡도는 O(n)으로 다음에 알아볼 KMP법의 최악의경우 시간 복잡도와 같다. 문자열 검색 자체가 무거운 작업이 아니기에 의외로 속도가 빠르다.
브루트-포스법 알아보기
텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용하여 검색하는 과정을 알아보자.
A. 텍스트의 첫 요소 'A'부터 시작한다. 패턴"ABC"가 텍스트의 0~2번 요소까지와 일치하는지 확인한다. 'A'와 'B'까지는 맞지만 'C'가 없어서 일치하지 않는다.
char[] text = {'A','B','A','B','C','D','E','F','G','H','A'};
// 일치 일치 불일치
char[] pattern = {'A','B','C'};B. 자 뒤로 옮겨서 텍스트의 두 번째 요소 'B'부터 연속된 3개를 조사한다. 일단 시작부터 'B'가 나오기 때문에 패턴과 일치하지 않으니 통과하고 한칸 더 옮겨보자.
char[] text = {'A','B','A','B','C','D','E','F','G','H','A'};
// X 불일치
char[] pattern = {'A','B','C'};C. 한칸 더 옮겨서 텍스트의 세 번째 요소 'A'부터 다시 조사한다.
이번엔 연속으로 나오는 요소들이 각각 'A','B','C'이기 때문에 패턴과 일치하여 검색에 성공하게 된다.
char[] text = {'A','B','A','B','C','D','E','F','G','H','A'};
// X X 일치 일치 일치
char[] pattern = {'A','B','C'};이와같이 브루트-포스법은 그저 텍스트의 요소를 한칸씩 옮겨가면서 패턴과 일치하는지 검사하는 매우 간단한 방법이며 선형 검색을 확장한 단순한 알고리즘으로 '단순법', '소박법'이라고도 한다.
※ 브루트-포스는 매우 다양한 분야에서 사용되는 단어인점 참고하자.
하지만 브루트-포스법은 이미 검사한 위치를 또 다시 검사하기에 효율이 좋지는 않다.
브루트-포스법 예제코드
public class BruteForce {
static int bfMatch(String txt, String pat) {
int pt = 0; // txt 커서
int pp = 0; // pattern 커서
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;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("텍스트: ");
String text = sc.next();
System.out.print("패턴: ");
String pattern = sc.next();
int idx = bfMatch(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()는 텍스트에서 패턴을 검색하여 성공하면 그 위치의 텍스트 쪽 인덱스를 반환한다. 텍스트에 패턴이 여러 개 있으면 맨 앞쪽에 위치한 텍스트쪽 인덱스를 반환하며, 검색 실패시 -1을 반환한다.
텍스트를 스캔하기 위한 변수로 pt(pointer text)를, 패턴을 스캔하기 위한 변수로 pp(pointer pattern)을 사용한다.
