Z 알고리즘(문자열 검색) 계산기

Z[i]는 문자열 s와 s[i..]가 앞에서부터 몇 글자나 같은지입니다. "aabxaayaab"에서 Z[7] = 3인 것은 7번째부터의 "aab"가 맨 앞의 "aab"와 세 글자 통째로 같다는 뜻입니다. Z[0]은 자기 자신이라 늘 전체 길이여서 뜻이 없습니다.

지금까지 본 것 중 가장 오른쪽까지 뻗은 일치 구간을 들고 다니며 값을 물려 쓰기 때문입니다. 새 자리가 그 구간 안에 있으면 이미 계산해 둔 값을 그대로 가져오면 되고, 글자를 실제로 견주는 것은 구간 밖으로 나갈 때뿐입니다. 늘린 만큼 구간의 오른쪽 끝이 오른쪽으로 가고 왼쪽으로 되돌아가지 않으므로, 늘려 본 총 횟수가 문자열 길이를 넘을 수 없습니다.

재는 것이 다릅니다. 실패함수 π[i]는 「s[0..i]의 접두사이면서 접미사인 가장 긴 길이」이고, Z[i]는 「s[i..]가 맨 앞과 겹치는 길이」입니다. 같은 사실을 다른 각도에서 본 것이라 서로를 만들어 낼 수 있으며, 이 도구는 Z 배열만으로 실패함수를 만들어 나란히 보여 줍니다.

패턴 + 구분자 + 본문을 이어 붙여 Z 배열을 만든 뒤, Z 값이 패턴 길이와 같은 자리를 찾으면 그것이 곧 매칭입니다. 본문을 한 번만 훑으면 끝나고 겹치는 매칭도 빠짐없이 나옵니다.

패턴과 본문이 이어 붙어 일치가 경계를 넘어가는 것을 막기 위해서입니다. 구분자는 패턴에도 본문에도 나오지 않는 글자여야 하며, 그러지 않으면 없는 매칭이 생기거나 있는 매칭이 어긋납니다. 이 도구는 겹치지 않는 글자를 자동으로 고르고, 직접 고른 구분자가 겹치면 계산하지 않고 이유를 알려 줍니다.

같은 글자나 같은 조각이 되풀이되는 입력에서 차이가 큽니다. "aaaaaaaa"처럼 반복이 심하면 한 글자씩 견주는 방법은 길이의 제곱에 가까운 비교가 필요한데, Z 알고리즘은 값을 물려 써서 거의 견주지 않습니다.

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