알고리즘

개념

원문과 패턴이 있을 때 서로 비교를 해보다가 매칭에 실패했을 때 성공한 부분을 다시 이용하여 이미 비교한 부분을 다시 비교하지 않도록 하자! (오른쪽으로 한칸 이동 X, 최대한 많이 이동)

실패함수

• F[i]는 P[1..i]에서, 접두사=접미사 이면서 가장 긴 것의 길이
• i+1번째 위치에서 매치가 실패하면, P[1..i]까지는 매치가 성공했다는 뜻이기 때문에 접두사와 접미사가 얼마나 일치하는지 알고 있으면 다시 비교를 안해도 됨

비교과정

처음에 원문의 a와 패턴의 b가 매칭이 실패하면 그 앞은 일치했다는 것이기 때문에 다 비교해 볼 필요가 없다 따라서 가장 앞에서 접두사와 접미사가 같은 지점까지 이동을 시키면 된다. 지금은 따라서 접두사 a가 접미사 a의 위치에 오도록 이동시킨다.

그 다음 비교를 하는데 b가 일치하지 않았다. 그 앞까지는 일치했다는 뜻이기 때문에 a와 일치하는 접미사를 찾아봐도 없기 때문에 다음 비교를 위해 패턴을 한칸만 이동한다.

시간복잡도

• 패턴 P에서 실패함수를 구하는 부분의 시간 복잡도는 O(M)
• 실패함수를 이용해서 원문에서 패턴이 일치하는 것을 찾는 시간 복잡도는 O(N)

따라서 O(N+M)