• 텍스트(text)에서 패턴(pattern)이 포함된 모든 위치를 찾는 문제
  • 텍스트는 긴 문자열, 패턴은 짧은 문자열

  • 문자열을 처음부터 끝까지 차례로 순회
  • 패턴 내의 문자들을 일일이 비교
  • 최악의 경우 두 비교군의 모든 패턴을 비교. O(MN)

p = "is"                       # 찾을 패턴
t = "This is a book~!"         # 전체 텍스트
M = len(p)                     # 찾을 패턴 길이
N = len(t)                     # 전체 텍스트 길이
 
def BruteForce(p, t):
    i = 0                      # t의 인덱스
    j = 0                      # p의 인덱스
    while j < M and i < N:     # j가 M보다 작고 i가 N보다 작은동안
        if t[i] != p[j]:       # 어떤 포인트와 포인트가 같지 않다면
            i = i - j          # 텍스트의 참조 위치 초기화(바로 뒤에서 i-j+1이 됨, 이전 조회 시작 위치+1)
            j = -1             # 패턴의 참조위치 -1으로 초기화(바로 뒤에서 0 됨)
        i = i + 1              # 일치하고 있었다면 조회 위치를 다음으로 넘김, 아니었다면 i=i-j+1, j=0
        j = j + 1
    if j == M:                 # j가 M, 즉 패턴이 전부 텍스트 내에 있으면
        return i - M           # 검색 성공; (시작 인덱스+패턴길이)에서 패턴길이 뺀, 즉 시작 인덱스 반환
    else:
        return -1              # 검색 실패

  • 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있다.
  • 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭 수행
  • 패턴을 전처리(배열 next[M]) → 잘못된 시작을 최소화
  • 시간 복잡도 : O(M+N)

생략

  • 오른쪽에서 왼쪽으로 비교
  • 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
  • 오른쪽 끝에 있는 문자가 불일치 & 문자가 패턴 내에 존재 X 한다면, 패턴의 길이만큼 이동
  • 오른쪽 끝에 있는 문자가 불일치 & 문자가 패턴 내에 존재 → 일치하는 패턴까지 단번에 이동

  • 찾고자하는 문자열 패턴의 길이 m, 총 문자열 길이 n일 때
  • 고지식한 패턴 검색 알고리즘 : O(m*n)
  • 카프 라빈 알고리즘 : O(n)
  • KMP 알고리즘 : O(n)

  • 앞의 두 매칭 알고리즘들의 공통점 : 문저를 적어도 한 번씩 훑는다 → 최선의 경우에도 Ω(n)
  • 보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 된다.
  • 발상의 전환 : 패턴의 오른쪽부터 비교
  • 최악의 경우 수행시간 : Θ(mn)
  • 입력에 따라 다르지만 일반적으로 Θ(n)보다 시간이 덜 든다.

O(n) : 최악의 경우 Θ(n) : 최악의 경우와 최선의 경우가 같은 증가율일 때 일반적으로 라는 의미 Ω(n) : 잘 해봐야 이정도라는 의미!


  • 줄리어스 시저가 사용했다는 암호
  • 알파벳을 일정한 문자 수만큼 평행이동
  • 모든 알파벳을 무차별적으로 밀어보는 전사공격에 취약

  • 문자 변환표를 이용한 암호화
  • 시저 암호화보다 강력
  • 알파벳마다 불규칙적인 다른 알파벳과 매칭
  • 복호화를 위해서는 모든 키의 조합(key space)가 필요

  • 배타적 논리합(exclusive-or) 연산 사용
  • 0과 1의 불규칙적인 나열로 된 암호키를 사용
  • 평문도 비트로 변환하여 암호키와 exclusive-or 처리
  • 복호화는 암호문을 다시 암호키와 exclusive-or 처리

  • 같은 값이 몇 번 반복되는가를 나타냄
  • ABBBBBBBBA → A1B8A1
  • Run-length encoding 알고리즘