라빈-카프 롤링 해시 계산기

창을 한 칸 옮길 때 해시를 처음부터 다시 계산하지 않고, 빠지는 글자를 빼고 들어오는 글자를 더해 갱신하는 방식입니다. h′ = ((h − s[i]·baseᵐ⁻¹)·base + s[i+m]) mod q 한 줄이면 되므로 창 하나당 O(1)이고 전체가 O(n)이 됩니다. 매번 다시 계산하면 O(nm)이라 단순 대조와 다를 것이 없습니다.

아닙니다. 서로 다른 문자열이 같은 해시로 떨어지는 충돌이 반드시 생깁니다. 그래서 라빈-카프는 해시가 맞은 자리마다 글자를 하나씩 대조해 확인해야 하고, 확인해 보니 아니었던 자리를 «가짜 일치»라고 부릅니다. 이 확인을 건너뛴 구현은 틀린 답을 내놓습니다.

가짜 일치가 급증해 O(n)이라던 것이 O(nm)으로 주저앉습니다. 이 도구의 기본 예문에서 q를 7로 두면 «the»를 찾는 데 가짜 일치가 10번 나지만, 101로 올리면 0번이 됩니다. 실전에서 10⁹ 근처의 큰 소수를 쓰는 이유입니다. 다만 답 자체는 달라지지 않습니다 — 글자 대조로 걸러 내므로 헛수고만 늘어납니다.

라빈-카프는 해시로 «아닌 자리»를 빠르게 건너뛰고, KMP는 패턴 안의 반복 구조를 미리 계산해 두었다가 어긋난 지점에서 되돌아갈 자리를 찾습니다. KMP는 최악의 경우에도 O(n+m)이 보장되지만, 라빈-카프는 충돌이 잦으면 느려질 수 있는 대신 여러 패턴을 한 번에 찾는 데 유리합니다.

됩니다. 글자를 코드 포인트 단위로 세므로 한글은 한 글자, 이모지도 한 글자로 셉니다. UTF-16 코드 단위로 세면 이모지 하나가 두 글자로 잡혀 찾은 위치가 어긋나는데, 그 문제를 피해 두었습니다.

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