[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 문자열 검색(브루트 포스법)

1. 문자열 검색이란?

문자열 검색(String searching)은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다. 이때 문자열을 텍스트, 찾아내는 문자열을 패턴이라고 한다.

 

2. 부르트 포스법으로 문자열 찾아내기

검색 알고리즘 중 가장 기초적이고 단순한 브루트 포스법(brute force method)부터 알아보도록 하겠다. 선형 검색을 단순하게 확장한 알고리즘이라 단순법이라고도 브루트 포스를 부르기도 한다.

 

#브루트 포스법으로 문자열 검색하기

def bf(txt,pat):
    pt = 0 #텍스트를 따라가는 커서
    pp = 0 #패턴을 따라가는 커서

    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1
            pp = 0
    return pt - pp if pp == len(pat) else -1

s1 = input("텍스트를 입력하세요.: ")
s2 = input("패턴을 입력하세요.")

idx = bf(s1,s2)

if idx == -1:
    print("텍스트 안에 패턴이 존재하지 않습니다.")
else:
    print(f"{(idx+1)}번째 문자가 일치합니다.")

 

 

3. 멤버십 연산자와 표준 라이브러리를 사용한 문자열 검색

파이썬에서는 문자열을 검색할 때 연산자, 표준 라이브러리를 사용해 구현할 수 있다.

 

• 멤버십 연산자로 구하기

• ptn in txt - ptn은 txt에 포함되어 있습니까?
• ptn not in txt - ptn은 txt에 포함되어 있지 않습니까?
  
  

 

• find, index 계열 함수로 구현하기

str 클래스형에 소속된 find( ), rfind( ), index( ), rindex( ) 함수는 문자열 검색을 하여 검색한 문자열의 위치를 반환한다.

str 클래스형	사용 방법	결과
find( )	str.find(sub[, start [, end]])	[start:end]에 sub가 포함되면 그 가운데 가장 작은 인덱스를 반환하고 그렇지 않으면 -1을 반환
rfind( )	str.rfind(sub[, start [, end]])	[start:end]에 sub가 포함되면 그 가운데 가장 큰 인덱스를 반환하고 그렇지 않으면 -1을 반환
index( )	str.index(sub[, start [, end]])	find( ) 함수와 같은 기능을 수행한다. 다만 sub가 발견되지 않으면 예외 처리로 ValueError를 내보낸다.
rindex( )	str.rindex(sub[, start [, end]])	rfind( ) 함수와 같은 기능을 수행한다. 다만 sub가 발견되지 않으면 예외 처리로 ValueError를 내보낸다.

 

• with 계열 함수로 구현하기

with 계열 함수는 어떤 문자열이 다른 문자열의 시작이나 끝에 포함되어 있는지를 판단합니다.

with 계열 함수	사용 방법	결과
startswith( )	str.startswith(prefix[, start [, end]])	- 문자열이 prefix로 시작하면 True, 그렇지 않으면 False를 반환한다.  - start가 지정되어 있으면 그 위치에서 판단하여 시작하고, end가 지정되어 있으면 그 위치에서 비교를 중지한다.
endswith( )	str.endswith(suffix[, start [, end]])	- 문자열이 suffix로 끝나면 True, 그렇지 않으면 False를 반환한다. - start가 지정되어 있으면 그 위치에서 판단하여 시작하고, end가 지정되어 있으면 그 위치에서 비교를 중지한다.

 

 

3. 문자열 검색 알고리즘의 시간 복잡도

	브루트 포스	KMP	보이어 · 무어
문자열 검색 알고리즘의 시간 복잡도	O(mn) - 일반적 경우 O(n) - 일부러 꾸며 낸 패턴이 아닌 경우	O(n) - 최악의 경우에도 이에 속하며 처리하기가 복잡하고 패턴 안에 반복이 없으면 효율성이 떨어지기 때문에 파일을 차례대로 읽어 들이며 검색하는 경우에 사용하면 좋다.	O(n) - 최악의 경우 O( n / m ) - 평균 배열을 만드는 데 복잡한 처리 과정이 필요해서 효율성이 덜어진다. 이때 배열을 1개를 만들어 사용하는 경우는 충분히 빠르지만 2개를 만들어 사용하는 경우엔 매우 효율성이 떨어진다.