04_week_KMP 알고리즘

단순 비교 방식을 사용하면 너무 많은 시간이 소요됨
ABCD에서 CD랑 겹치는걸 찾는다 라고 가정하면
1.
ABCD
CD
2.
ABCD
CD
3.
ABCD
CD
로 시간복잡도가 O(N*M) 이됨

KMP (Knuth-Morris-Pratt)

만든 사람의 이름을 딴 알고리즘
접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일 수 있는지를 판별하여 매칭할 문자열을 빠르게 점프하는 기법

ex)
abacaaba가 있을 경우
접두사 접미사

여기서 구해야 할 것은 접두사와 접미사가 일치하는 최대 길이

sudo code

def KMP(): # 실패함수 구현
    N=len(string_A)
    table=[0]*N # string_A 길이 만큼 초기화
    j=0
    for i in range(N): # 모든 문자열을 검사하면서
        while (j>0 and string_A[i] != string_A[j]): # i번째와 j가 일치하지 않는다면 j에서 1을 뺀 값으로 이동시켜버림
            j=table[j-1] 
        if string_A[i]==string_A[j]: # 둘이 일치하면 i번째 idx에 j에 1을 더한 값을 넣음
            table[i]=j+1
    return table

위와 같이 하나씩 접두사와 접미사를 늘려가며 비교하닥 일치하지 않는 경우가 발생하면 일치했던 부분까지 되돌아가서 다시 검사를 하는 방식