[Algorithm] KMP 알고리즘을 알기 전에 LPS에 대해 알아보기

소개

패턴 매칭. 원래는 KMP 알고리즘을 알기 전에, 아호-코라식 알고리즘을 우선적으로 알게 되었다. 하고있는 프로젝트에서 문장을 가지고 특정 문자열이 포함되어 있는 찾아야 했다. 하지만, 일반적인 브루트 포스 방식으로 한다면 시간이 오래 걸릴 것이란 것을 알고 있다. 그래서 제미나이가 나에게 아호-코라식 알고리즘을 소개해주었다. 알아보니 아호-코라식 알고리즘을 알기전에 KMP 알고리즘이 사용되기 때문에 그것을 먼저 알 필요가 있었다.

문자열 패턴 매칭은 다음과 같은 예시로 설명할 수 있다.

"The rain in Spain stays mainly in the plain" (영화 "마이 페어 레이디" 중)
rain, Spain, mainly, plain 과 같이 ain 패턴이 많기 때문에, 단순 브루트 포스는 시간이 많이 걸린다.

LPS는 Logest Prefix which is also Suffix의 약자로 문자열 중 부분 문자열이면서 가장 긴 접두사이자 접미사를 의미한다. 즉, 접두사 = 접미사이고 가장 긴 부분 문자열이다. "abjkdfab"에서 접두사 = 접미사인 문자열은 "ab"이다. 그런데, 단순히 "abjkdfab"를 저장하는 게 아닌 문자열의 첫 시작 부분부터 "a", "ab", "abj", ..., "abjkdfab" 순으로 하나씩 늘려가며, 그 문자열에 LPS에 해당되는 문자열의 길이를 각 자리에 저장한다.

input: 문자열
output: 각 부분 문자열의 길이 (list)

(ex)
[a, b, a, b, c, a, b, a]
[0, 0, 1, 2, 0, 1, 2, 3]

원리

1. LPS 패턴의 길이가 들어갈 리스트를 만들어준다.
   
   
2. j=0, i=1 인덱스부터 시작하, i는 뒷쪽 문자만 보고 j는 알고리즘을 통해 i 보다 앞에 있는 문자열과 비교한다.
   
   
3. 비교하는 패턴이 같으면 j와 i를 동시에 1씩 올려주고, pi[i] 자리에 j를 저장한다. 이 때 j는 부분 문자열의 크기를 나타낸다. 즉, 인덱스 만큼 이동을 했다는 것은 순회를 하면서 패턴이 같다왔음을 의미한다.
   
   
4. 패턴이 같지 않다면, j를 초기화를 해주는데 0으로 바로 초기화하지 않는다. j의 이전 인덱스 (=같았을 때 부분 문자열의 크기)만큼만 이동해주는 것이다. i가 비교하기 전에 있는 (접미사) 부분 문자열 문장들이 같다면, 그 같은 부분은 생략해도 되기 때문이다. 예를들어, "abcaaxabcab"에서 "abca"는 이미 비교가 완료되니, j->"a", i->"b"를 비교하고 있을테다. 이때 "abca"도 이미 "a"를 LPS로 가지고 있기 때문에, "abcaaxabc(a) b"와 "(a) bcaaxabcab" 인덱스는 이미 중복된 상태일수도 있다. "a(b)caaxabca(b)"는 같은 문자이므로 앞문자인 "a"는 중복이 되고, pi에 j에 저장되어 있기 때문에 뒤로 더 이동하지 않고 중간부터 시작할 수 있다.
   
   
5. 이를 각 부분 문자열을 순서대로 진행해주면 된다.

 

디버깅

for (int i = 1; i < pattern_len; i++) {
	// ...
    while (j > 0 && pattern[i] != pattern[j]) {
        j = pi[j - 1];
    }
}

 j>0은 범위가 벗어나지 않도록 한거라서 깊게 생각안해도 된다. 
패턴이 같지 않으므로  j = 0이 된다.

for (int i = 1; i < pattern_len; i++) {
	// ...
    if (pattern[i] == pattern[j]) {
        j++;
        pi[i] = j;
    }
}

패턴이 같으므로 j는 1 올려주고, pi에 저장한다.

이 지점이 

while (j > 0 && pattern[i] != pattern[j]) {
    j = pi[j - 1];
}

의 궁금증을 해소시켜 줄 것이다.

"b"랑 "a"는 다르므로 j=pi[4-1] 자리로 가게된다. j=1인데 왜 그렇냐면 이전에 부분 문자열이 "abca"까지만 맞았는데, "abca"만 볼 때 이 문자열에 대해서도 "a" 문자가 접두사=접미사 역할을 하기 때문이다. "[abca] ax [abca] b"에서 "[abca] ax [abca] b"로 색칠된 부분이 이미 공통이기 때문에 그 앞에 있는 "[abca] ax [abca] b"에서 "b"를 한번 더 반복해서 봐야하기 때문이다. 여기서 만약 패턴이 맞다면 앞에 있는 a는 j=1이라는 정보에서 앞에 1만큼 크기가 채워져 있다는 정보가 이미 저장되어 있어서 더 돌아가지 않아도 되기 때문이다. 이 맥락이 이해된다면, 첫음 비교할 때도 같은 매커니즘이라는 것을 알게 될 것이다. 맨처음에도 사실 이런 매커니즘이다. "abcaaxabcab". 다만 while문에서 이미 저 패턴은 false 이기 때문에 바로 와닿지 않기 때문이다. "abcaaxabcab"이 패턴이 더 긴 문자열에서 발견되었다면, 예컨대, "abcaa......abcab...."이런 문자열이 있었다면 j=4이기 때문에 4을 이미 먹고 시작해도 되는 의미로 받아들이면 된다.

코드 및 시각화 

알고리즘

// --- Longest Prefix which is also Suffix --- 
// 문자열 중 부분 문자열들 중 가장 긴 접두사이자 접미사
// 접두사 = 접미사인 가장 긴 부분 문자열
// abjkdfab -> "ab" = "ab"
// -------------------------------------------
// input: 문자열
// output: 부분 문자열 길이
// -------------------------------------------
// 참고 자료: https://ymg5218.tistory.com/152


#include <iostream>
#include <vector>

using namespace std;

vector<int> create_pi(string pattern) {
    // [a, b, a, b, c, a, b, a]
    // [0, 0, 0, 0, 0, 0, 0, 0]
    int pattern_len = pattern.size();
    vector<int> pi(pattern_len, 0);

    int j = 0;

    // a
    // ab
    // aba
    // ...
    // ababcaba 순으로 하나씩 비교
    for (int i = 1; i < pattern_len; i++) {
        // 비교하는 패턴이 다를 때
        // j는 접두사쪽
        // i는 접미사쪽
        // j = pi[j - 1]인 이유는,
        // 현재 비교하는 접미사 앞쪽이랑 
        // 똑같은 접두사 앞 다음이 같은 지 비교함.
        // 그러면 그곳이 또 다르면 또 그 안에 부분 접미사와 같은 부분 접두사와 비교,
        // 만약 같다면 다시 그곳부터 시작하는 것.
        // 왜냐하면 줄어든 접미사 만큼 접두사가 같으니까.
        
        //      j       i
        // abca ax abca bc

        //    j  ←  j           i  
        // [a bc a] ax [a bc a] bc       

        // 해당 부분에서 i=j="b"로 같으므로 여기서부터 count 하면된다.
        // 왜냐하면 부분 접두사의 접두사인 "a"와 부분 접미사의 접미사 "b"가
        // 같은 문자열이고 크기가 j에 담기기 떄문. (j = pi[j-1])
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }

        // 비교하는 패턴이 같을 때
        if (pattern[i] == pattern[j]) {
            j++;
            pi[i] = j;
        }
    }

    return pi;
}

int main() {
    vector<int> pi = create_pi("ababcaba");
    // vector<int> pi = create_pi("abcaaxabcabc");

    for (auto p : pi)
        printf("%d ", p);

    return 0;
}

 

시각화

import pygame
import sys

WHITE = (255, 255, 255)
BLACK = (30, 30, 30)
RED = (255, 50, 50)     # i: 접미사 (Suffix)
BLUE = (50, 50, 255)    # j: 접두사 (Prefix)
YELLOW = (255, 255, 150) 
GREEN = (0, 150, 0)
GRAY = (180, 180, 180)

class KMPVisualizer:
    def __init__(self, pattern):
        # 1. 화면 설정
        pygame.init()
        self.width = 1200
        self.height = 600
        self.screen = pygame.display.set_mode((self.width, self.height))
        pygame.display.set_caption("KMP Failure Function Visualizer")
        
        self.font = pygame.font.SysFont("arial", 35, bold=True)
        self.msg_font = pygame.font.SysFont("arial", 22)
        
        self.pattern = pattern
        self.n = len(pattern)
        
        # 2. 변수 초기화 함수 호출
        self.reset_state()

    def reset_state(self):
        """데이터만 초기화하는 함수"""
        self.pi = [0] * self.n
        self.i = 1
        self.j = 0
        self.message = "Press SPACE to step through | Press R to Reset"
        self.done = False

    def draw(self):
        self.screen.fill(WHITE)
        
        box_size = 70
        margin = 20
        total_width = self.n * (box_size + margin) - margin
        start_x = (self.width - total_width) // 2
        start_y = 250

        # --- 접두사/접미사 테두리 ---
        if not self.done:
            padding = 10 
            
            # Prefix Box (파란색): 0 ~ j
            p_end_x = start_x + self.j * (box_size + margin) + box_size
            p_rect = pygame.Rect(
                start_x - padding, 
                start_y - padding, 
                (p_end_x - start_x) + 2*padding, 
                box_size + 2*padding
            )
            pygame.draw.rect(self.screen, BLUE, p_rect, 4, border_radius=15)
            
            # Suffix Box (빨간색): (i-j) ~ i
            s_start_idx = self.i - self.j
            s_start_x = start_x + s_start_idx * (box_size + margin)
            s_end_x = start_x + self.i * (box_size + margin) + box_size
            s_rect = pygame.Rect(
                s_start_x - padding - 5,
                start_y - padding - 5, 
                (s_end_x - s_start_x) + 2*(padding + 5), 
                box_size + 2*(padding + 5)
            )
            pygame.draw.rect(self.screen, RED, s_rect, 4, border_radius=15)

        # 텍스트 그리기
        self.draw_text("KMP 'PI' Array Construction", (self.width//2, 50), BLACK, center=True)
        self.draw_text(self.message, (self.width//2, 500), BLUE if "Match" in self.message else RED, center=True)
        self.draw_text("Space: Next | R: Reset", (self.width//2, 550), GRAY, center=True)

        for idx in range(self.n):
            x = start_x + idx * (box_size + margin)
            y = start_y
            
            rect = pygame.Rect(x, y, box_size, box_size)
            
            if not self.done and (idx == self.i or idx == self.j):
                pygame.draw.rect(self.screen, YELLOW, rect)
            
            pygame.draw.rect(self.screen, BLACK, rect, 3)
            
            char_text = self.font.render(self.pattern[idx], True, BLACK)
            text_rect = char_text.get_rect(center=(x + box_size//2, y + box_size//2))
            self.screen.blit(char_text, text_rect)
            
            idx_text = self.msg_font.render(str(idx), True, GRAY)
            self.screen.blit(idx_text, (x + 25, y - 30))

            pi_val = self.pi[idx]
            color = GREEN if idx < self.i else GRAY
            pi_text = self.font.render(str(pi_val), True, color)
            self.screen.blit(pi_text, (x + 25, y + 80))

        if not self.done:
            i_x = start_x + self.i * (box_size + margin) + box_size // 2
            self.draw_pointer(i_x, start_y - 55, RED, "i (Suffix)", direction="down")
            
            j_x = start_x + self.j * (box_size + margin) + box_size // 2
            self.draw_pointer(j_x, start_y + box_size + 140, BLUE, "j (Prefix)", direction="up")

        pygame.display.flip()

    def draw_text(self, text, pos, color, center=False):
        img = self.msg_font.render(text, True, color)
        if center:
            rect = img.get_rect(center=pos)
            self.screen.blit(img, rect)
        else:
            self.screen.blit(img, pos)

    def draw_pointer(self, x, y, color, label, direction="down"):
        if direction == "down":
            pygame.draw.polygon(self.screen, color, [(x, y+10), (x-10, y-10), (x+10, y-10)])
            pygame.draw.line(self.screen, color, (x, y-10), (x, y-40), 5)
            self.draw_text(label, (x - 40, y - 70), color)
        else:
            pygame.draw.polygon(self.screen, color, [(x, y-10), (x-10, y+10), (x+10, y+10)])
            pygame.draw.line(self.screen, color, (x, y+10), (x, y+40), 5)
            self.draw_text(label, (x - 40, y + 50), color)

    def step(self):
        if self.i >= self.n:
            self.done = True
            self.message = "Visualization Finished! Press R to restart."
            return

        if self.j > 0 and self.pattern[self.i] != self.pattern[self.j]:
            self.message = f"Mismatch! j returns to pi[{self.j}-1] ({self.pi[self.j-1]})"
            self.j = self.pi[self.j-1]
        else:
            if self.pattern[self.i] == self.pattern[self.j]:
                self.j += 1
                self.pi[self.i] = self.j
                self.message = f"Match! Prefix Length: {self.j}"
                self.i += 1
            else:
                self.pi[self.i] = 0
                self.message = "No match. i moves forward."
                self.i += 1

    def run(self):
        clock = pygame.time.Clock()
        while True:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    pygame.quit(); sys.exit()
                if event.type == pygame.KEYDOWN:
                    if event.key == pygame.K_SPACE:
                        self.step()
                    if event.key == pygame.K_r or event.unicode == 'ㄱ':
                        self.reset_state()
            self.draw()
            clock.tick(30)

if __name__ == "__main__":
    visualizer = KMPVisualizer("abcaaxabcabc")
    visualizer.run()

참고자료

1. 민규링. (2024, 10, 10). [알고리즘] 패턴 매칭 알고리즘, KMP 알고리즘 (Knuth–Morris–Pratt Algorithm). 민규의 흔적. https://ymg5218.tistory.com/152

[알고리즘] 패턴 매칭 알고리즘, KMP 알고리즘 ( Knuth–Morris–Pratt Algorithm )