[Do it! 자료구조, 알고리즘 Python] 7장. 문자열 검색

- 문자열 검색 : 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면ㅇ ㅓ디에 위치하는지 찾아내는 것.

 

1. 브루트 포스법 : 선형 검색을 단순하게 확장한 알고리즘 -> 효율 안좋음.

#브루트 포스법으로 문자열 검색
>>> def bf_match(txt: str, pat: str) -> int:
	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
    
    if __name__ == '__main__':
	s1 = input('텍스트 입력:')
	s2 = input('패턴 입력:')
	
	idx = bf_match(s1, s2)  #문자열 S1~S2르 ㄹ브루트 포스법으로 검색
	
	if idx==-1:
		print('텍스트 안에 패턴이 없다')
	else:
		print(f'{(idx+1)}번째 문자가 일치함')
        
        
텍스트 입력:ABGCEDDA
패턴 입력:EDD
5번째 문자가 일치함
>>>

 

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

str.find(sub[, start[, end]])
# sub가 포함되면 그 가운데 가장 작은 인덱스를 반환, 아니라면 -1을 반환
# end만 생략 / start와 end 같이 생략 가능
# start는 슬라이스의 시작 인덱스이며 기본값은 0, end는 슬라이스 끝 인덱스이며 기본값은 시퀀스의 길이
# []는 그 안의 인수가 생략가능함을 의미

str.rfind(sub[, start[, end]])
# [start:end]에 sub 포함되면, 가장 큰 인덱스 반환, 아니라면 -1 반환

str.index(sub[, start[, end]])
# find() 함수와 같은 기능 수행
# sub 발견 안되면 예외 처리로 ValueError 출력

str.rindex(sub[, start[, end]])
# rfind()와 같은 기능
# sub 발견 안되면 예외처리로 ValueError 출력

 

with 계열 함수로 구현하기

str.startswtich(prefix[, start[, end]])
# 문자열이 prfix로 시작하면 True, 아니라면 False를 반환
# start가 지정되어 있으면 그 위치에서 판단 시작
# end가 지정되어 있으면 그 위치에서 비교 중지

str.endswtich(suffix[, start[, end]])
# 문자열이 suffix로 시작하면 True, 아니라면 False를 반환
# start가 지정되어 있으면 그 위치에서 판단 시작
# end가 지정되어 있으면 그 위치에서 비교 중지

 

2. KMP법 : 텍스트와 패턴 안에서 겹치는 문자열을 찾아내, 검사를 다시 시작할 위치를 구해 패턴의 이동을 되도록 크게하는 알고리즘 -> 알고리즘은 복잡한데 보이어, 무어법보다 성능에서 낮다. 그래서 별로 사용 안함.

# KMP법으로 문자열 검색하기
def kmp_match(txt: str, pat: str) -> int:
	pt=1
	pp=0
	skip=[0]*(len(pat)+1)
	#건너뛰는 표 만들기
	skip[pt]=0
	while pt!=len(pat):
		if pat[pt]==pat[pp]:
			pt += 1
			pp +=1
			skip[pt] = pp
		elif pp==0:
			pt += 1
			skip[pt] =pp
		else:
			pp=skip[pp]
	#문자열 검색하기
	pt = pp= 0
	while pt != len(txt) and pp != len(pat):
		if txt[pt] == pat[pp]:
			pt += 1
			pp += 1
		elif pp==0:
			pt+=1
		else:
			pp=skip[pp]
	return pt - pp if pp == len(pat) else-1

>>> if __name__ == '__main__':
	s1=input('텍스트 입력:')
	s2=input('패턴 입력:')
	idx=kmp_match(s1,s2)
	if idx == -1:
		print('텍스트 안에 패턴 존재 안함')
	else:
		print(f'{(idx+1)}번째 문자 일치함')

		
텍스트 입력:abdeabcd
패턴 입력:abc
5번째 문자 일치함

 

3. 보이어/무어법 : 패턴의 끝문자에서 시작해 앞쪽으로 검사 수행, 이 과정에서 일치 안하는 문자 발견시 미리 준비한 표를 바탕으로 패턴이 이동하는 값 결정함.

# 보이어, 무어법으로 문자열 검색하기(문자열 길이는 0~255개)
>>> def bm_match(txt:str, pat:str) -> int:
	skip=[None]*256 #건너뛰기표
	#표 만들기
	for pt in range(256):
		skip[pt]=len(pat)
	for pt in range(len(pat)):
		skip[ord(pat[pt])]=len(pat)-pt-1
	#검색하기
	while pt<len(txt):
		pp=len(pat)-1
		while txt[pt]==pat[pp]:
			if pp==0:
				return pt
			pt -=1
			pp-= 1
		pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat)-pp\
		      else len(pat)-pp
	return -1

>>> if __name__ == '__main__':
	s1=input('텍스트 입력:')
	s2=input('패턴 입력:')
	idx=bm_match(s1,s2)
	if idx == -1:
		print('텍스트 안에 패턴 존재 안함')
	else:
		print(f'{(idx+1)}번째 문자 일치함')

		
텍스트 입력:ABABCDEFGHA
패턴 입력:ABC
3번째 문자 일치함

 

일반적으로 파이썬에서 문자열검색하려면 표준 라이브러리를 사용하는 것을 추천함..