[Algorithm][KMP] 28. Find the Index of the First Occurrence in a String

KMP 알고리즘이란?

 문자열을 한개씩 비교하는 것이 아니라 지금까지 비교한 문자열 중 접두사, 접미사가 같을 경우 중간 과정을 생략하고 비교하는 알고리즘

 

시간 복잡도

\( O(n + m) \)

 

문제 링크

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

---

 이번 문제는 주어진 문자열에서 sub 문자열이 몇번 째 index에 존재하는지를 답안으로 내야합니다. 단순하게 생각하면 단순 문자열 비교로 보일 수 있지만, 주어진 조건을 보면 문자열의 길이가 10000입니다. 그래서 단순 비교를 한다면 당연히 시간초과가 발생합니다.

 

 

단순 전체 비교 방법

 

 우선 단순 비교로 문제를 푸는 방법을 소개하겠습니다. 전체 문자열의 시작 문자부터 Sub 문자열의 문자를 하나씩 비교합니다. 이렇게 Sub 문자열의 전체가 일치할 때까지 진행합니다. 단순 비교의 시간 복잡도는 전체 문자열의 크기 \( N \) 만큼 for 문을 사용하고 Sub 문자열의 크기 \( M \) 만큼 for문을 사용하기 때문에 \( O(NM) \) 가 됩니다. 이 때 \( M \) 의 크기가 \( N \)이 된다면 \( O(N^2) \) 까지도 증가하게 됩니다. 아래 예시에서는 총 14번의 문자 비교가 필요합니다.

 

KMP 알고리즘 방법

 

 우리는 위의 경우처럼 전체 문자열 N개를 하나하나 비교하고 싶지 않습니다. 효율적으로 비교가 필요 없는 부분은 아래처럼 생략하며 진행하고 싶습니다. 하지만 아래처럼 sub 문자열을 다시 처음부터 비교시키기엔 예외 상황이 있습니다. 바로 지금까지 비교해서 일치한 문자열 중 중복되는 문자열이 존재하는 경우입니다. 이러한 예외 상황을 고려해 효율적으로 중간 과정을 생략한 알고리즘이 바로 KMP 알고리즘입니다.

 

 KMP 알고리즘의 핵심은 지금까지 연속으로 일치한 문자열에서 접두사와 접미사가 같은 경우가 있을 때 중간 과정을 생략하고 접미사를 접두사의 위치로 점프시키는 것입니다. 접두사와 접미사를 사용하는 이유는 위에서 말한 중복 상황을 고려하기 위함입니다. 글로는 이해가 어려울 수 있습니다. 아래 그림에서 단순 비교 방법과 비교하여 원리를 알면 더 이해하기 쉬울 것입니다.

 KMP 알고리즘은 문자열 비교 중 일치하지 않는다면, 이전 문자열에서 접두사와 접미사 길이를 확인하고 접미사 다음 문자로 다시 비교합니다. 그림과 같이 접미사 부분인 "ab"를 제외하고 "c"부터 일치 여부를 다시 검사합니다.

 그렇다면 만약 여기서 sub 문자열의 접미사 다음 문자가 일치하지 않는 문제가 발생하면 어떻게 될까요?  그러면 접미사를 다시 "Sub 문자열2" 로 생각하고 "Sub 문자열2" 에서 서로 일치하는 접미사와 접두사를 찾고 해당 접미사 다음 문자열부터 비교하면 됩니다. 만약 없다면 Sub 문자열 처음부터 다시 비교하면 됩니다.

 

접두사, 접미사가 일치하는 최대 길이 계산

 

 위의 KMP 알고리즘을 적용하기 위해 Sub 문자열의 각 문자열 위치에서 접두사, 접미사가 일치하는 최대 길이를 사전에 계산합니다. 이 때 이 값을 "Longest Proper Prefix which is Suffix"라고 하여 LPS 배열이라고 부릅니다. 하지만 LPS 배열을 계산할 때 주의할 점은 Sub 문자열 또한 결국에는 문자열의 비교 과정이기 때문에 위에서 소개한 원리가 그대로 적용이 됩니다. LPS 배열의 이전 index 값들을 이용하여 LPS 배열의 새로운 index 값을 구합니다. 

 

 

Python

 그래서 KMP 알고리즘을 적용한 LeetCode 28번 문제의 풀이 코드는 아래와 같습니다.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        lps = [0] * len(needle)
        
        j = 0
        for i in range(1,len(needle)):
            while not( j == 0 or needle[i] == needle[j] ):
                j = lps[j-1]
                
            if needle[i] == needle[j]:
                j += 1
                lps[i] = j
                
        j = 0
        for i in range(0,len(haystack)):
            while not( j == 0 or haystack[i] == needle[j] ):
                j = lps[j-1]
                
            if haystack[i] == needle[j]:
                if j == len(needle)-1:
                    return i - j
                j += 1
        return -1