KMP 실패함수·문자열 검색 계산기

패턴의 각 자리까지에서 「진접두사이면서 동시에 접미사인 가장 긴 문자열의 길이」입니다. 예를 들어 ABABCABAB의 마지막 자리 값은 4인데, 앞 4자 ABAB와 뒤 4자 ABAB가 같기 때문입니다. 어긋났을 때 이 길이만큼은 이미 맞은 것으로 치고 건너뛸 수 있어 본문을 되돌려 읽지 않아도 됩니다. 부분일치 테이블, LPS 배열이라고도 부릅니다.

진접두사는 자기 자신을 뺀 접두사이기 때문입니다. 글자가 하나뿐이면 자기 자신 말고는 접두사가 없으므로 길이가 0이 됩니다. 이 규칙을 빼먹고 π[0]을 1로 두면 표 전체가 한 칸씩 어긋나 검색이 무한히 돌 수 있습니다.

규약이 달라서일 뿐 둘 다 맞습니다. 이 계산기는 0부터 세는 배열에 「길이」를 담는 흔한 규약을 씁니다. 원논문에 가까운 서술은 f[i] = π[i] − 1로 두어 −1이 등장하고, 1부터 세는 교재는 값이 한 칸씩 밀려 보입니다. 표에 −1이 있으면 다른 규약이며, 담긴 정보는 같습니다.

아닙니다. 최악의 경우가 O(n+m)으로 보장되는 것이지 언제나 비교를 덜 하는 것은 아닙니다. 본문에 패턴의 첫 글자가 드물면 브루트포스도 본문을 거의 한 번만 훑어 비교 횟수가 비슷합니다. 차이는 「앞부분이 길게 맞다가 뒤에서 어긋나는」 자료에서 벌어지며, AAAA…AAB에서 AAAAB를 찾는 경우가 대표적입니다.

찾습니다. AAAAA에서 AA를 찾으면 0, 1, 2, 3 네 곳이 모두 나옵니다. 패턴 전체가 맞으면 j를 0으로 되돌리지 않고 π[m−1]로 낮추기 때문이며, 그래서 앞선 일치와 겹치는 자리도 놓치지 않습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.