[Algorithm] KMP 알고리즘

 

 

34강에 대한 리뷰

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12363

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

 

대표적인 문자열 매칭 알고리즘

 

모든 경우를 비교하지 않아도 부분 문자열을 찾아줌

 

접두사와 접미사의 개념을 활용함: 접두사와 접미사가 일치하는 최대 길이를 구함

 

 

 

 

 

 

** Python

 

def make_table(pattern):
    pattern_len = len(pattern)
    table = [0 for i in range(pattern_len)]
    j = 0
    for i in range(1, pattern_len):
        while j != 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table
    
if __name__ == "__main__":
    p = "abacaaba"
    t = make_table(p)
    print(t)

 

 

 

 

def make_table(pattern):
    pattern_len = len(pattern)
    table = [0 for i in range(pattern_len)]
    j = 0
    for i in range(1, pattern_len):
        while j != 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table

def kmp(parent, pattern):
    table = make_table(pattern)
    parent_len = len(parent)
    pattern_len = len(pattern)
    j = 0
    for i in range(parent_len):
        while j > 0 and parent[i] != pattern[j]:
            j = table[j - 1]
        if parent[i] == pattern[j]:
            if j == (pattern_len - 1):
                print(f'{i - pattern_len + 2} 번째에서 찾았습니다')
                # print(i - pattern_len + 2)
                j = table[j]
            else:
                j += 1

if __name__ == "__main__":
    pr = "ababacabacaabacaaba"
    pt = "abacaaba"
    # t = make_table(pt)
    # print(t)
    kmp(pr, pt)