KMP 알고리즘 : 문자열 검색 알고리즘 (백준-16916)

 

▶N문자열에서 M문자열을 검색할 때?

가장 단순한 문자열 검색 : O(NM)

KMP 알고리즘 : O(N+M)

 

[PI 배열]

pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이

(이때 prefix가 0~i  까지의 부분 문자열과 같으면 안된다.)

 

[KMP 알고리즘]

- j-1번째 까지 탐색을 했는데 문자열이 일치 했고 j번째 문자열에서 i번째 문제열과 다를 경우

 -> 0~j-1번째 까지의 pi배열에서 패턴이 있는지 확인한다.

 -> 즉 pi[j-1]값이 있는지 확인(코드에서는-> j>0 이 부분)

     1,  k라는 값이 있다면 j는 k라는 값을 가지게 되고 j번째 문자열과 i번째 문자열을 비교한다!

       => 이 때 j가 0보다 큰데 s[i] 와 pattern[j]의 문자열이 같게되면 ? -> 0~j-1번쨰 까지는 문자열이 같기 때문에 비교할 필요 없다.

     2. 값이 0일 경우는 pattern의 0부터 다시 비교해야됨

def getPI(pattern):
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j

def KMP(s, pattern):
    getPI(pattern)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != pattern[j]:
            j = pi[j - 1]
        if s[i] == pattern[j]:
            if j == len(pattern) - 1:
                return True
            else:
                j += 1
    return False

s = input()
pattern = input()
pi = [0 for x in range(len(pattern))]

if KMP(s, pattern):
    print('1')
else:
    print('0')

 

 

[출처]

https://landlordgang.tistory.com/82

https://bowbowbow.tistory.com/6