문자열 A에 문자열 B(A의 길이 N, B의 길이 M, N ≥ M)가 포함되었는지 확인하는 작업을 $O(N+M)$ 시간에 끝내는 알고리즘.
문자열을 $O(M^2)$ 방식으로 구하는 것에서, B의 접두사와 A의 접미사가 같은 구간이 있다면, 그 구간은 검색하지 않고 건너뛸 수 있지 않을까?
문자열 검색을 실패했을 때, 다음 검색 시작 위치와 맞은 개수의 offset을 찾기 위해 건너뛰어야 하는 값을 기록하고 있는 배열을 반환한다.
i번째에서 접두사와 접미사를 비교해 가장 큰 크기를 사용
그러니까 자기 자신으로부터 최대 크기의 접미사의 크기를 저장하는 배열을 만들어낼 수 있다.
~까지 봤을 때 맞고, 이 다음에 다르다면. 여기까지 맞았다는 건 source의 접두사부터 개수 만큼 맞았다는 말. source의 접두사부터 맞은 개수까지를 봤을 때 여기서 최대크기의 접두사를 skip하는 데에 이용할 수 있다. 이건 점진적으로 만들어오면 이미 최대 크기가 되어 있다. 이 값을 이용하자.
현재 비교 중인 suffix에 prefix 부분을 갖다 댄다고 생각해보자. 비교하는 부분이 틀리다면, 다음으로 prefix가 같은 부분이 나올 때까지 그대로 더 앞쪽으로 이동하는 형태를 생각하면 된다. 그러려면 prefix가 어디까지 이동하면 될지 알아야 하는데,
failure 배열의 값을 갱신할 때는 src[s + m] == src[m] 일 때인데, 이 때 s는 비교하는 문자의 값이 일치하는 경우 중 가장 m이 큰 값이 나올 수 있을 때다. 왜냐하면 s는 값이 1로 가장 작을 때부터 답이 되는 순간 배열에 기록해나가기 때문이다.
비교하다 값이 틀리면, 지금까지 맞춰 온 배열의 matched 개를 만든 s가 존재한다.
귀납적으로 고민해볼까?