• 패턴의 마지막 문자부터 text와 비교
• Text와의 비교 문자가 pattern에 없는 문자면 M만큼 비교를 스킵 가능

얼마나 비교를 스킵해야 하는가?

패턴에 해당 비교 문자가 없는 경우

txt의 e에서 미스매치가 발생했지만, e는 패턴에 존재하지 않는다

미스매치가 발생한 다음 인덱스로 패턴을 옮긴다

패턴에 비교 문자가 존재하는 경우

미스매치가 발생했지만, 패턴에는 b가 존재한다.

이 경우 가장 오른쪽의 b의 인덱스를 미스매치가 발생한 열에 맞춘다. 왜냐하면 b가 여러개 존재할수도 있기 때문에 !!

하지만, 다음과 같은 경우가 발생할수도 있다.

패턴에 비교 문자가 존재하지만, 옮기면 인덱스가 오히려 뒤로 움직인다

위의 경우, b가 미스매치가 발생하였고, 패턴 가장 오른쪽에 있는 b는 현재 비교하고 있는 인덱스보다 뒤에 있다!!

그러면 비교 인덱스가 오히려 뒤로 당겨지게 된다… 이를 해결하기 위해서 이 상황에서는 브루트 포스처럼 한칸씩만 앞으로 가도록 한다.