[Python] SW Expert Academy - 4864. 문자열 비교

SW Expert Academy 4864번 문자열 비교 문제는 두 개의 문자열이 주어질 때, 첫 번째 문자열이 두 번째 문자열 내에 존재하는 지를 알아내는 문제이다. 난이도는 D2이며 패턴 매칭 알고리즘 중에 Brute Force, KMP가 아닌 보이어 무어 알고리즘을 사용하였다.

 

SW Expert Academy 4864번 문자열 비교 문제 정보

알고리즘 분류

- 보이어 무어 Boyer Moore, 패턴 매칭 Pattern Matching 알고리즘

난이도

- D2

 

문자열 비교 문제 요약

• 길이가 N인 문자열 str1과 길이가 M인 str2가 주어진다.
• N의 범위는 5 이상 100 이하, M의 범위는 10 이상 1000 이하이며, M이 N보다 크거나 같다.
• str2(문자열) 내에 st1(패턴)이 존재하면 1 존재하지 않으면 0을 출력한다.

문제 풀이 과정

• 패턴 내의 문자 들을 역으로 저장한 건너뛰기 리스트를 정의한다.
• 패턴을 발견하거나 탐색을 실패할 때까지
• 1) 현재 비교 문자가 패턴 내에 존재하는 경우:
  1. 비교 문자와 같다면 이전 index의 문자를 비교한다.
  2. 비교 문자와 다르다면 skip 리스트의 index 만큼 비교 인덱스를 건너뛴다.
• 2) 현재 비교 문자가 패턴 내에 존재하지 않는 경우: 패턴 길이만큼 비교 인덱스를 건너뛴다.
• 패턴 매칭에 성공하면 1을, 실패하면 0을 반환한다.
• 테스트 케이스 번호, 패턴 존재 여부를 출력한다.

코드 및 설명

• skip [] - 건너뛰기 정보를 담은 리스트 (index: 건너뛰기 칸 수, value: 패턴 내의 문자)
• matchCnt - 매칭 된 문자 개수
• nowIndex - str2에서의 현재 비교 인덱스

# 보이어-무어 알고리즘
def boyer_moore(pattern, text):
    skip = list(reversed(pattern))

    matchCnt = 0
    nowIndex = len(str1) - 1

    # 패턴 매칭 검색
    while matchCnt != len(str1) and nowIndex < len(str2):
        if str2[nowIndex] in skip:
            if str2[nowIndex] == skip[matchCnt]:
                matchCnt += 1
                nowIndex -= 1
                continue
            else:
                nowIndex += skip.index(str2[nowIndex])
                matchCnt = 0
        else:
            nowIndex += len(str1)
            matchCnt = 0

    if matchCnt == len(str1):
        return 1
    if nowIndex >= len(str2):
        return 0

T = int(input())
for tc in range(T):
    str1 = input()
    str2 = input()

    print("#%d %d" % (tc + 1, boyer_moore(str1, str2)))

---

SW Expert Academy 4864번 문자열 비교 문제는 패턴 매칭 알고리즘에 관한 문제이며 파이썬으로 보이어 무어 알고리즘을 구현하였다. 난이도는 D2지만 패턴 매칭 알고리즘을 구현하는 것이 조금 어려웠다. Brute Force, KMP 알고리즘도 공부해봐야겠다.