KMP 알고리즘

KMP 알고리즘은 문자열 검색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 문자열에서 다른 문자열을 검색할 때, 매번 전체 문자열을 처음부터 끝까지 일일이 비교하지 않아도 되도록 하는 것이 목표입니다. 이를 위해서 KMP 알고리즘은 패턴 문자열을 미리 분석하여 LPS 배열을 계산하고, 이를 이용하여 문자열 검색을 수행합니다.

 

예를 들어, "ABABDABACDABABCABAB"이라는 문자열에서 "ABABCABAB"이라는 패턴을 검색하고자 한다고 가정해봅시다. 먼저 KMP 알고리즘은 패턴 문자열인 "ABABCABAB"을 분석하여 LPS 배열을 계산합니다. 이때, LPS 배열은 아래와 같이 계산됩니다.

• i = 0: A, LPS[0] = 0
• i = 1: AB, LPS[1] = 0
• i = 2: ABA, LPS[2] = 1 (앞의 A와 뒤의 A가 동일)
• i = 3: ABAB, LPS[3] = 2 (앞의 AB와 AB가 동일)
• i = 4: ABABC, LPS[4] = 0
• i = 5: ABABCA, LPS[5] = 1
• i = 6: ABABCAB, LPS[6] = 2
• i = 7: ABABCABA, LPS[7] = 3
• i = 8: ABABCABAB, LPS[8] = 4 (앞뒤의 ABAB가 동일)

패턴 문자열 : ABABCABAB
LPS 배열     : 00120123