- 완전검색 Brutal force Exhaustive
그냥 한 칸 씩 패턴을 밀면서 타깃(본문)과 비교, 틀렸을 때의 정보를 활용 안 하고 무작정 한 칸씩만 이동 비효율, 시간 복잡도 무려 O(MN) (N = 본문 타깃 길이, M은 패턴 길이)
def BruteForce(p, t):
# N: 본문(t)의 전체 길이, M: 찾으려는 패턴(p)의 길이
N = len(t)
M = len(p)
i = 0 # t(본문)를 훑는 인덱스
j = 0 # p(패턴)를 훑는 인덱스
# 본문 끝에 도달하거나, 패턴을 완전히 찾을 때까지 반복
while j < M and i < N:
# [불일치 발생 시]
if t[i] != p[j]:
# i를 이번 비교를 시작했던 위치의 '다음 칸'으로 되돌림
# i - j는 비교 시작점이고, 아래에서 i + 1을 해주므로 결과적으로 시작점+1이 됨
# 본문 인덱스 - 패턴 인덱스니까 비교가 딱 시작한 곳
i = i - j
# j는 패턴의 맨 처음으로 되돌림 (-1로 세팅 후 아래에서 +1 하면 0이 됨)
j = -1
# [공통 실행]
# 1. 일치하면: 다음 글자를 비교하기 위해 둘 다 전진
# 2. 불일치하면: 위에서 세팅한 위치(i-j, -1)에서 1씩 더해져 다음 시도 시작
i = i + 1
j = j + 1
# [결과 반환]
if j == M:
# j가 패턴 길이(M)와 같아졌다면 모든 글자가 일치했다는 뜻
# i는 마지막 일치 후 +1이 된 상태이므로, i - M을 하면 패턴의 시작 인덱스가 나옴
return i - M # 검색 성공
else:
return -1 # 본문 끝까지 갔으나 검색 실패- KMP
반면 이 경우는 패턴 자체의 반복되는 정보를 이용 = pi 테이블 예를 들어 ABABAB가 패턴이라면 AB라는 묶음이 패턴 안에서 반복됨,
LPS
LPS는 패턴 안에서 반복되는 뭉치 중 가장 긴 길이, 본문과 패턴 일치 안 하면 이 길이만큼 shift
로직:
투 포인터 방식,
i패턴을 끝까지 훑으며 LPS를 기록, 현재 검사하는 위치는 1부터 시작
j는 지금까지 일치한 ‘접두사의 길이’이자 다음에 비교할 ‘인덱스’임, 0부터 시작
- 패턴 문자에서 index인 i를 전진시키며
pattern[j]와 비교, 즉 검사 위치에서 한 칸 이전 문자와 비교. - 이전 문자 중 i와 일치하는 덩어리가 있으면 j를 1 늘려 기록
- 불일치하면 j를 이전 일치 지점
(lps[j-1])으로 되돌려 중복 비교 j는 지금 막 틀린 위치고,j-1은 바로 직전까지 일치했던 마지막 위치, 고로 j가 0이 아니라lps[j-1]로 가는 이유는 그 성공했던 덩어리 안에서 앞뒤가 같은 가장 긴 길이이기 때문에, 이전까지 맞았던 덩어리 속에, 혹시 맨 앞이랑 똑같이 생긴 작은 덩어리가 또 있었나? 하고 확인 → 실패하면 지금까지 맞았던 접두사가 끝나는 부분으로 가서 반복 연산 피하자는 의도
예시)
| i | 패턴 | j | 비교 (pattern[i] vs pattern[j]) j가 i보다 한 글자 전 | lps[i] | j의 움직임 |
|---|---|---|---|---|---|
| 0 | A | 0 | (첫 글자) | 0 | 시작점 |
| 1 | A | 0 | A == A (일치) | 1 | j가 1로 증가 (다음 비교는 1번 인덱스) |
| 2 | B | 1 | B != A (불일치) | 0 | j가 lps[0](0)으로 후퇴 후 종료 |
| 3 | A | 0 | A == A (일치) | 1 | 다시 j가 1로 증가 |
| 4 | A | 1 | A == A (일치) | 2 | j가 2로 증가 (다음 비교는 2번 인덱스) |
| 5 | A | 2 | A != B (불일치!) | 2 | j가 lps[1]인 1로 후퇴→ pattern[1](A)와 다시 비교해 보니 일치!→ 최종 j는 2가 됨 (AA가 앞 뒤로 반복) |
검사하는 i 값이 한 번 커지면 다시 작아지지 않음! 시간 복잡도 O(M+N) (N = 본문 타깃 길이, M은 패턴 길이)
def KMP_search(t, p):
# ---------------------------------------------------------
# 1. pi 테이블(LPS)을 만드는 내부 함수 (패턴 분석 단계)
# ---------------------------------------------------------
def get_pi(pattern):
m = len(pattern)
pi_table = [0] * m
j = 0 # 접두사(Prefix) 인덱스
for i in range(1, m): # i는 접미사(Suffix) 인덱스
# 글자가 다르면, 이전에 일치했던 위치(pi_table[j-1])로 j를 되돌림
while j > 0 and pattern[i] != pattern[j]:
j = pi_table[j - 1]
# 글자가 같으면, 일치하는 길이를 증가시키고 기록
if pattern[i] == pattern[j]:
j += 1
pi_table[i] = j
return pi_table
# ---------------------------------------------------------
# 2. 본문에서 패턴을 찾는 실제 로직 (검색 단계)
# ---------------------------------------------------------
n = len(t)
m = len(p)
pi = get_pi(p) # 위에서 만든 함수로 pi 테이블을 먼저 생성
j = 0 # 패턴의 인덱스
# i(본문 인덱스)는 0부터 끝까지 전진만 함 (되돌아가지 않음!)
for i in range(n):
# 현재 본문 글자와 패턴 글자가 다르면 j를 점프시킴
while j > 0 and t[i] != p[j]:
j = pi[j - 1] # pi 테이블을 보고 "중복되는 앞부분"으로 이동
# 글자가 같으면
if t[i] == p[j]:
# 패턴의 끝까지 다 확인했다면 (검색 성공)
if j == m - 1:
return i - m + 1 # 패턴이 시작된 인덱스 반환
else:
j += 1 # 다음 글자 확인을 위해 패턴 인덱스 증가
return -1 # 끝까지 다 봤는데 못 찾은 경우
# --- 사용 예시 ---
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
result = KMP_search(text, pattern)
if result != -1:
print(f"패턴이 인덱스 {result}에서 시작됩니다.")
else:
print("패턴을 찾지 못했습니다.")- 보어스 무어
여기도 마찬가지로 반복을 줄이기 위함, 대신 여기는 패턴 뒤에서부터 비교
- 패턴 맨 끝 위치의 본문 문자가 패턴 안에 없으면 전체 문자열 길이만큼 shift → 연산 줄일 수 있음
- 패턴 맨 끝 위치의 본문 문자가 맨 끝 패턴 문자와 다르지만 패턴 안에 있으면 (전체 패턴 길이 - 그 글자 index)만큼 shift
ex)
water (패턴) e (본문)→ 이러면 e는 water에서 4번째에 위치해 있지만 패턴이 1칸 (5-4) 뒤로 이동해야 본문과 위치가 겹침 - 맨 끝 문자가 서로 같으면 바로 앞 문자 비교
시간 복잡도 O(M+N)
(feat. SWEA 4864 문자열 비교) 보어스 무어 구현한 예제 코드
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
p = input()
len_p = len(p)
p_end = len_p - 1 #index니까 -1
# 전처리: p를 역순 dict로 미리 받아둔다, dict 컴프리헨션으로 for 문 돌면서 역 index 저장
p_dict = {char: (p_end - i) for i, char in enumerate(p)}
# 무한 루프 방지: p_dict에서 가져온 값이 0일 경우 shift가 안 변할 수 있어요.
# 처음 index = 0인 위치에서 패턴 비교시는 괜찮은데
# (index = 0인 경우: 맨 끝 글자가 타깃과 비교 되므로 타깃과 패턴 글자가 일치한 것으로 판단 -> if문으로 빠짐)
# 만약 그 위치에서 마지막 글자 일치해서 잘 가다가 else문으로 빠지면
# index 값인 0만 계속해서 shift에 더해지므로 무한루프 -> index = 0일때만 shift 1 더해주기
t = input()
shift = 0
answer = 0
while shift <= len(t) - len(p): #shift값 len(t)와 같거나 작을 때 -> 조건 위험
#shift값이 len(t)-len(p)보다 작거나 같아야 무한 루프 안 걸림
#왜 len(t)를 기준으로 하면 안 될까?
#1. Index Error: t[shift + p_end]를 계산할 때 타깃의 범위를 벗어나서 프로그램이 죽을 수 있다.
#2. 불필요한 연산: 정답이 나올 수 없는 구간(남은 글자가 패턴보다 적은 구간)까지 굳이 검사하게 된다.
#타깃 알파벳과 패턴 맨 마지막 알파벳 일치 여부 확인
if p[p_end] == t[shift+p_end]: #일치
#이 위치에 p_end -= 1넣으면 1글자짜리 index = 0인건 들어오자 마자 -1되어서 체크가 안 됨
if p_end ==0 and p[0] == t[shift]: #p_end가 0까지 와야만 맨 앞과 끝 문자만 보고 통과시키는 일이 없어짐
answer = 1
break
else:
p_end -= 1
#print [shift]
else: #불일치
p_end = len_p - 1
if t[shift+p_end] not in p_dict.keys(): # 타깃 알파벳이 패턴에 없음
shift += len_p
else: # 타깃 알파벳이 패턴에 있음
if p_dict[t[shift+p_end]] == 0: #index = 0 무한 루프 방지
shift += 1
else:
shift += p_dict[t[shift+p_end]]
else:
answer = 0
print (f"#{test_case} {answer}")나쁜 문자 이동 (Bad Character Heuristic)
비교하다가 본문과 패턴의 문자가 다를 때, 그 본문의 문자를 나쁜 문자라고 한다. 근데 이 나쁜 문자가 패턴 안에 여럿 있을 수도 있다
ex) ANANAS (패턴) A (본문) 이런 식으로 S자리에 A가 왔는데, A가 패턴 안에 여러 번 있다.
그럼 어떻게 하는가? 불일치가 일어난 지점보다 왼쪽에 있으면서 (앞에 있으면서) 가장 오른쪽에 있는 문자(가장 뒤에 있는 문자)에 맞춘다: 가장 보수적으로, 정답 건너 뛰지 않게 가장 조금 shift함.
시간 복잡도 보통 O(N) 미만, 최악의 경우 고지식 방법과 같은 O(MN). 최고는 O(N/M) (N = 본문 타깃 길이, M은 패턴 길이)