String (2)

• 패턴 매칭

문제를 검색하는 것!

ex) 고지식한 패턴 검색 알고리즘, 카프-라빈 알고리즘, KMP 알고리즘, 오이어-무어 알고리즘 등

 

• 고지식한 알고리즘

본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내 문자들을 일일이 비교한다.

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:
        if t[i] != p[j]:
            i = i - j
            j = -1
            # 불일치하면 패턴과 텍스트를 하나씩 어긋나게 해서 비교
        i = i + 1
        j = j + 1
    if j == M :
        return i - M    # 검색 성공
    else :
        return -1       # 검색 실패

 

문자열 비교를 고지식한 알고리즘을 이용하여 푼다면?

def f(pat, txt, M, N):
    for i in range(N-M+1):  # text에서 비교 시작 위치
        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 알고리즘

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는 지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 수행한다.

패턴을 전처리해서 잘못된 시작을 최소화 한다.

패턴이 불일치할 경우 고지식하게 바로 뒤 인덱스로 한칸 이동하는 것이 아니라 일부 패턴이 똑같은 것을 발견한 부분으로 점프해서 거기서부터 새로 비교를 시작하는 것!

ex)

abcdabcd…

abcdabce….

마지막에 d, e 가 달라서 불일치가 발생 → 하지만 바로 뒤 b로 비교 위치가 이동하지 않고

abc가 반복되는 [4] 인덱스 위치부터 비교를 한다!

def kmp(t, p):
    N = len(t)
    M = len(p)
    lps = [0] * (M+1)
    # preprocessing
    j = 0   # 일치한 개수 = 비교할 패턴 위치
    lps[0] = -1
    for i in range(1, M):
        lps[i] = j      # p[i] 이전에 일치한 개수
        if p[i] == p[j]:
            j += 1
        else:
            j = 0
    lps[M] = j
    # search
    i = 0   # 비교할 텍스트 위치
    j = 0   # 비교할 패턴 위치
    while i < N and j <= M:
        if j == -1 or t[i] == p[j]:     # 첫글자가 불일치 했거나, 일치하면
            i += 1
            j += 1
        else:   # 불일치
            j = lps[j]
        if j == M:  # 패턴을 찾을 경우
            print(i-M, end=' ')     # 패턴의 인덱스 출력
            j = lps[j]

    print()
    return

 

• 보이어 무어 알고리즘

오른쪽에서 왼쪽으로 비교한다.

대부분의 상용 소프트웨어에서 채택하고 있다.

지금까지와는 다르게 패턴의 오른쪽 끝 글자부터 비교를 해서 일치하는 글자를 찾아 매칭한다.

오른쪽 끝 문자와는 불일치하지만 패턴 내에 일치하는 문자가 있으면 그 문자와 매칭하게 이동함.

반복하는 매커니즘

1. 오른쪽 끝 문자 일치함?
2. 오른쪽 끝 문자와는 달라도 패턴 내에 일치하는 문자 있음? → 그 문자랑 매칭해서 다시 비교
3. 위 두 단계를 거쳐도 일치하는 문자가 없으면 패턴 길이만큼 건너뛰고 다시 비교한다!

앞의 매칭 알고리즘들과 달리 보이어 무어는 텍스트 문자열의 문자들을 모두 최소 한번씩 훑지 않아도 된다. 건너뛰는 문자들이 있기 때문이다.

패턴의 오른쪽부터 비교한다는 발상의 전환이 반영되었다.

 

• 문자열 암호화

시저 암호 → 문자열 수평이동을 이용한 암호

문자 변환표를 이용한 암호화 (단일 치환 암호)

 

• bit열의 암호화

배타적 논리합 연산 사용

y 가 1이면 x 값이 바뀌고 0이면 그대로다.

x = 0 XOR y = 0 → XOR = 0

x = 0 XOR y = 1 → XOR = 1

x = 1 XOR y = 0 → XOR = 1

x = 1 XOR y = 1 → XOR = 0

 

• 문자열 압축

Run-length encoding 알고리즘

같은 값이 몇 번 반복되는가를 나타냄으로써 압축

abbbba → a1b4a1

 

• 중요한 패턴 알고리즘들 (보충)

1. KMP
2. 카프 - 라빈
3. 보이어 - 무어

요런 것들이 있다. 하지만 일단은 이런게 있다고 알아두고 고지식한 패턴 매칭을 구현해보자!

결국 고지식한 패턴 매칭 문제는 이전에 풀었던 구간합 문제 풀이 원리와 비슷하다.

특정 구간끼리 서로 비교하기 때문에!

패턴이 존재할 수 있는 가능한 모든 시작 위치를 구한다!

 

• 회문을 검사하는 알고리즘

# 1. 문자열의 회문 검사
arr = 'abcdeddcba'  # True
M = len(arr)
# M//2 만큼 반복해서 비교
s = 0
e = M - 1
isOk = True
for i in range(M//2):
    # arr[s + i] != arr[e - i]
    if arr[s + i] != arr[e - i]:
        isOk = False
        break
print(isOk)

# 2. 길이 N인 문자열 내에 모든 가능한 길이 M인 문자열 조사
N = 8
M = 4
arr = 'CBBCBAAB'
print(arr)
for s in range(N-M + 1):
    e = s + M - 1
    for i in range(M//2):
        if arr[s + i] != arr[e - i]:
            break
    else:
        print(arr[s: s + M])