문자열 검색
문자열 검색이란?
문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다.
종류
문자열 검색하는 방법에는 여러 가지가 있는데 그 중에서 몇가지만 살펴 보도록 하겠습니다.
- Brute-Force, String Built-In Function
- Trie
- Rabin-Karp
- KMP법
- Boyer-Moore법
이렇게 5가지를 살펴볼 것이다.
1번의 경우 가장 기본적인 방식이기도 하고 간단하기 때문에 해당 페이지에서 정리하도록 하겠습니다.
브루트-포스법
브루트-포스법이란?
브루트 포스법은 말 그대로 brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다.
완전 탐색 알고리즘으로 선형 검색을 확장한 알고리즘이다. 단순법, 소박법이라고도 불리는 이 방식은 가능한 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져옵니다. 이 알고리즘이 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다는 것입니다.
문자열 검색 파트에서는 설명하기 쉽게 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하겠습니다.
비교 과정을 보면 다음과 같습니다.
- 텍스트의 첫문자 ‘A’, ‘B’는 일치하고 ‘C’는 다릅니다.
- 패턴을 1칸 뒤로 옮긴뒤 텍스트의 2번쨰 문자부터 3개의 문자가 일치하는지 조사합니다. ‘B’와 ‘A’가 다릅니다.
- 패턴을 다시 1칸뒤로 옮깁니다. ‘A’, ‘B’, ‘C’가 모두 일치합니다.
해당 방식에서 1번 비교 과정에서 0번, 1번, 2번 Index를 확인 했으므로 텍스트의 문자를 0 ~ 2번까지 스캔한 것이다. 하지만 2번 에서 1번 Index를 다시 확인하고 3번의 경우에도 2번 Index를 다시 확인합니다. 즉, 이미 검사를 진행한 위치를 기억하지 못하는 것입니다. 이러한 이유 때문에 브루트-포스법의 효율은 좋지 않다고 할 수 있습니다.
코드
int bfMatch(String txt, String pat) {
int pt = 0, pp = 0;
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;
}String-Built-In Function
String 내장 함수 사용
java.lang.String 클래스는 문자열을 검색하는 indexOf 메소드와 lastIndexOf 메소드를 제공합니다.
- int indexOf(String str)
- int indexOf(String str, int fromIndex)
- int latIndexOf(String str)
- int lastIndexOf(String str, int fromIndex)
위의 메소드는 모두 지정한 문자열(str)이 포함되어 있는지 검색합니다. 1, 3번은 모든 문자열에 대해서 검색하고, 2, 4번은 fromIndex부터의 문자열에 대해서 검색합니다. 이때, 3, 4는 같은 문자열에 대해서 가장 마지막 위치의 문자열을 검색합니다. 검색에 성공하면 찾은 문자열(텍스트)의 인덱스를 반환하고 실패하면 -1을 반환합니다.
indexOf() 동작 방식
Java에서 함수의 구조를 파악해 봤는데, 다음과 같았다.
일단, 현재 본문 문자열 text를 value라고 뒀고, 패턴 문자열 pattern을 str로 뒀다.
그 이후, 문자열의 길이가 0인 경우에 false를 출력하게 하고 아니면 다음과 같이 실행하기 시작한다.
- str[0] 문자를 가져오고 value.length - str.length의 Index까지 탐색 시작
- str[0] 문자를 i번 index에서 발견시 j = i + 1이라고하고, value는 j부터 str은 index 1에 있는 문자부터 문자열 비교
- end = j + str.length - 1 이라고 할때 j == end까지 비교가 끝났을 경우 해당 문자열이 있는 것이므로 return i;
확인해본 결과 그렇게 좋은 방식으로 구현되어 있지는 않은 것 같습니다.
Reference
