KMP/ ROBIN KMP

KMP 알고리즘

글자의 패턴을 미리 저장해둔다.

 

매칭이 안된 글자의 직전 패턴값을 참조하여 그 인덱스의 문자를 다시 비교한다.

 

 

그러니깐 숫자 2를 통해 ab 의 패턴이 이전에 있던 것을 알 수가 있으니  그 패턴 이후부터 비교할 수 있는 거다.

 

 

접두사 접미사 일치하는 한 가장 큰 길이 만큼 이동

 

 

ROBIN  KMP 

 

WINDOW SLICE 를 사용하여

해쉬값이 일치하는 지 확인하고 마지막으로 해쉬 충돌을 피하기 위해 글자를 비교한다.

 

Leetcode 28 , 796