패턴 매칭
패턴 매칭에 사용되는 알고리즘들
고지식한 패턴 검색 알고리즘
비효율적이긴 하나 구현할 줄 알아야 함
고지식한 패턴 검색 알고리즘의 시간 복잡도
-
최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨
-
길이가 10000인 문자열에서 길이 80인 패턴을 찾는다고 할 때, 최악의 경우 약 10000* 80 = 800000 번의 비교가 일어난다.
-
비교 횟수를 줄일 수 있는 방법은 없는가?
def f(pat, txt, M, N):
for i in range(N-M+1): #txt에서 비교 시작 위치
for j in range(M):
if txt[i+j] != pat[j]: # 불일치면 다음 시작 위치로
break
else: # 패턴 매칭에 성공하면
return 1
# 모든 위치에서 비교가 끝난 경우
return 0
T = int(input())
for tc in range(1, T+1):
pat = input()
txt = input()
M = len(pat)
N = len(txt)
ans = f(pat, txt, M, N)
print(f'#{tc} {ans}')KMP 알고리즘
-
불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대해서 다시 비교하지 않고 매칭을 수행
-
패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화 함
-
next[M] :불일치가 발생했을 경우 이동할 다음 위치
-
시간 복잡도 : O(M+N)
보이어 -무어 알고리즘
문자열 암호화
시저 암호 (Ceaser cipher)
-
줄리어스 시저가 사용했다고 하는 암호이다.
-
시저는 기원전 100년경에 로마에서 활약했던 장군이다.
-
시저 암호에서는 평문에서 사용되고 있는 알파벳을 일정한 문자 수 만큼 [평행이동] 시킴으로써 암호화를 진행한다.
