📚 문제
두 개의 문자열 str1과 str2가 주어진다. 문자열 str2 안에 str1과 일치하는 부분이 있는지 찾는 프로그램을 만드시오.
예를 들어 두 개의 문자열이 다음과 같이 주어질 때, 첫 문자열이 두번째에 존재하면 1, 존재하지 않으면 0을 출력한다.
ABC
ZZZZZABCZZZZZ
두번째 문자열에 첫번째 문자열과 일치하는 부분이 있으므로 1을 출력.
ABC
ZZZZAZBCZZZZZ
문자열이 일치하지 않으므로 0을 출력.
[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다. (1≤T≤50)
다음 줄부터 테스트 케이스 별로 길이가 N인 문자열 str1과 길이가 M인 str2가 각각 다른 줄에 주어집니다. (5≤N≤100, 10≤M≤1000, N≤M)
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
보이어 무어 알고리즘을 사용해서 풀어 보았다. 패턴 문자열의 맨 끝부터 비교하며 현재 비교하는 문자가 패턴 문자열의 끝과 같으면 거꾸로 패턴과 같은지 확인한다. 같으면 종료시키고 다르면 한 칸 전진한다. 현재 비교하는 문자가 패턴 문자열 안에 없으면 패턴의 길이만큼 이동시키고 문자열 안에 있으면 그 문자까지 이동시켜 해결해나가는 알고리즘이다.
📒 코드
# 보이어 무어 알고리즘
T = int(input())
for tc in range(1, 1+T):
pattern = input() # 패턴
string = input() # 패턴이 있는지 확인할 문자열
p_l = len(pattern) # 패턴의 길이
s_l = len(string) # 문자열의 길이
i = p_l - 1 # 패턴의 뒤부터 비교
is_str = 0 # 패턴이 문자열에 존재하는지 확인
while i < s_l:
if string[i] == pattern[-1]: # 패턴의 끝과 문자가 같을 때
for j in range(p_l): # 패턴의 끝이 같을 때 패턴과 역순으로 비교해서 다 같은지 확인
if string[i-j] != pattern[-1-j]: # 다르면 1만큼 이동
i += 1
break
else:
is_str = 1 # 패턴이 문자열에 존재
i = s_l # 있으니 반복문을 종료
else: # 문자와 패턴의 끝이 다를 때
for j in range(1, p_l):
if string[i] == pattern[-1-j]: # 패턴 내의 같은 문자를 찾아 거기까지 이동
i += j
break
else: # 패턴 내에 없으면 패턴의 길이만큼 이동
i += p_l
print(f'#{tc} {is_str}')🔍 결과 : Pass
passionate developer