KMP

• https://www.youtube.com/watch?v=yWWbLrV4PZ8
• https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&referrerCode=0&searchKeyword=KMP

---

1. 패턴 테이블(실패함수)을 구한다.

접두사     접미사
-----     -----
a b a c a a b a

우리가 구해야 할 것은 위와 같이 패턴 데이터에서 접두사와 접미사가 일치하는 최대 길이이다.

a	b	a	c	a	a	b	a
0	0	1	0	1	1	2	3

max(패턴 테이블) == 3 : abacaaba 에서 2번 이상 나타나는 부분 문자열들 중 가장 긴 부분 문자열의 길이

2. KMP 문자열 매칭 과정

긴 글(string): ababacabacaabacaaba
찾을 문자열(pattern): abacaaba

1. 먼저 긴 글과 찾을 문자열을 하나씩 비교
   
2. 서로 다른 문자가 발견되면 일치하는 접두사 크기에 한해서만 부분 문자열의 인덱스를 이동시킨다 (table을 이용)
   
3. 다시 하나씩 비교
   
4. 일치하는 부분문자열을 발견하면 반복문을 종료하거나 계속 찾을 수 있다.
   

전체 코드

def get_pattern_table(p):
    table = [0 for _ in range(len(p))]
    j = 0  # j : 접두사 체크
    for i in range(1, len(p)):  # i : 접미사 체크
        while j > 0 and p[i] != p[j]:  # 만약 접두사와 접미사 부분(i,j)이 다르다면
            j = table[j - 1]  # j를 한칸 뒤로 이동(j-1) -> (j-1)위치의 테이블 값으로 j를 이동시킨다 
        if p[i] == p[j]:  # 접두사와 접미사 부분이 같다면
            j += 1  # 접두사 체크변수 j를 +1 , 접미사 체크변수 i는 어차피 for문에서 +1
            table[i] = j  # i 위치에 현재까지의 동일한 접두사, 접미사 길이를 적어둔다
    return table
    
    
def kmp(s, p):
    ptable = get_pattern_table(p)
    count = 0
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = ptable[j - 1]
        if s[i] == p[j]:
            if j == len(p) - 1: 
            # s에서 p를 찾은 상태
            # j가 p의 마지막에 위치하면 s에서 p를 찾은 것이다.
                count +=1
                j = ptable[j]
                # return True
            else:
            # 아직 매칭중이기 때문에 j를 +1 한다.
                j += 1
    return count # s에서 찾은 p의 개수
    
    
s = input() # 긴 글
p = input() # 찾을 패턴

시간복잡도
O(N + M)