[자바 Do It! 알고리즘]Chapter07 문자열 검색 (브루트-포스법)

[문자열 검색이란?]

1. 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다.

2. 예를 들어 문자열 "STRING", "KING" 에서는 "IN"을 검색하면 문자열 검색에 성공합니다. 하지만 문자열 "QUEEN"에서 "IN"을 검색하면 문자열 검색에 실패합니다. 그러면 지금부터는 이해하기 쉽게 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하겠습니다.

​

[브루트-포스법]

1. 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해 검색하는 순서입니다..

ABABCDEFGHA

ABC

1) 텍스트의 첫 문자 'A'부터 시작하는 3개와 문자와 "ABC"가 일치하는지 검사합니다. 'A'와 'B'는 일치하고 'C'는

다릅니다.

ABABCDEFGHA

ABC

2) 패턴을 1칸 뒤로 옮깁니다. 텍스트의 2번째 문자부터 3개의 문자가 일치하는지 조사합니다. 'A'와 'B'가

다릅니다.

ABABCDEFGHA

ABC

3) 패턴을 다시 1칸 뒤로 옮깁니다. 'A', 'B', 'C' 모두 일치합니다.

2. 브루트-포스법은 선형검색을 확장한 알고리즘이므로 단순법, 소박법이라고도 합니다.

3. 이미 검사를 진행한 위치를 기억하지 못하므로 브루트-포스법의 효율은 좋지 않다고 할 수 있습니다.

브루트-포스법

브루트-포스법 결과

[String.indexOf 메서드로 문자열 검색하기]

1. java.lang.String 클래스는 문자열을 검색하는 indexOf 메서드와 lastIndexOf 메서드를 제공합니다.

1	int indexOf(String str_
2	int indexOf(String str, int fromIndex)
3	int lastIndexOf(String str)
4	int lastIndexOf(string str, int fromIndex)

2. 위의 메서드는 모두 지정한 문자열(str)이 포함되어 있는지 검색합니다.

1,3은 모든 문자열에 대해서 검색하고 2,4는 fromIndex 부터의 문자열에 대해서 검색합니다.

이 때, 3,4는 같은 문자열에 대해서 가장 마지막 위치의 문자열을 검색합니다.

검색에 성공하면 찾은 문자열(텍스트)의 인덱스를 반환하고 실패하면 -1을 반환합니다.

프로그램을 실행하면 반각 문자는 1바이트의 바이트 배열로, 전각 문자는 3바이트의 바이트 배열로 바꾸어 출력합니다. 따라서 바뀐 배열의 길이를 length 메서드를 사용하면 검색 대상의 무낮가 1바이트인지 3바이트인지 알 수 있습니다. 이 값을 for문을 반복하여 누적한 다음 s2의 길이를 더해 완성합니다.