보이어-무어 문자열 검색 계산기
본문과 패턴을 넣으면 오른쪽 끝에서 왼쪽으로 견주며 나쁜 문자 규칙으로 얼마나 건너뛰는지 창마다 보입니다. 한 번도 읽지 않고 지나친 글자 수를 세어, 패턴이 길수록 빨라지는 이유를 숫자로 확인할 수 있습니다.
43글자 · 400글자까지
7글자 · 60글자까지
읽지 않고 지나친 글자
28글자
본문 43글자 가운데 65.1%를 한 번도 보지 않았습니다. 창을 8번 대며 16번 견줬고, 단순 대조라면 48번 견줘야 합니다.
마지막 출현 표
| 글자 | 패턴에서 마지막 자리 |
|---|---|
| ␣ (공백) | 2 |
| H | 4 |
| A | 5 |
| T | 6 |
여기 없는 글자는 −1로 봅니다. 창의 j번째에서 어긋났고 그 자리의 본문 글자가 c라면 미는 폭 = max(1, j − last[c])입니다. 뜻은 「패턴 안의 c를 본문의 c에 맞춰 대라」이고, max로 1을 씌우는 것은 last[c]가 j보다 오른쪽일 때 값이 음수가 되어 창이 뒤로 가 버리기 때문입니다.
창을 대는 과정
1. 자리 0 · 견줌 1번 · 7칸 밀기
어긋난 자리의 본문 글자 「F」가 패턴에 아예 없습니다. 그 글자를 덮는 정렬은 모두 헛수고라 7칸을 한 번에 밉니다 — 지나친 6글자는 읽지도 않습니다.
2. 자리 7 · 견줌 1번 · 4칸 밀기
「 」는 패턴의 2번 자리에 있습니다. 그 자리를 본문의 「 」에 맞춰 대려면 6 − 2 = 4칸을 밉니다.
3. 자리 11 · 견줌 2번 · 6칸 밀기
어긋난 자리의 본문 글자 「L」가 패턴에 아예 없습니다. 그 글자를 덮는 정렬은 모두 헛수고라 6칸을 한 번에 밉니다 — 지나친 5글자는 읽지도 않습니다.
4. 자리 17 · 견줌 1번 · 4칸 밀기
「 」는 패턴의 2번 자리에 있습니다. 그 자리를 본문의 「 」에 맞춰 대려면 6 − 2 = 4칸을 밉니다.
5. 자리 21 · 견줌 7번 · 1칸 밀기 · 일치
7글자가 모두 맞았습니다. 겹치는 일치를 놓치지 않으려고 한 칸만 밉니다.
6. 자리 22 · 견줌 1번 · 4칸 밀기
「 」는 패턴의 2번 자리에 있습니다. 그 자리를 본문의 「 」에 맞춰 대려면 6 − 2 = 4칸을 밉니다.
7. 자리 26 · 견줌 1번 · 7칸 밀기
어긋난 자리의 본문 글자 「N」가 패턴에 아예 없습니다. 그 글자를 덮는 정렬은 모두 헛수고라 7칸을 한 번에 밉니다 — 지나친 6글자는 읽지도 않습니다.
8. 자리 33 · 견줌 2번 · 6칸 밀기
어긋난 자리의 본문 글자 「S」가 패턴에 아예 없습니다. 그 글자를 덮는 정렬은 모두 헛수고라 6칸을 한 번에 밉니다 — 지나친 5글자는 읽지도 않습니다.
아래 줄이 지금 대어 본 패턴입니다. 짙은 글자는 실제로 견준 자리이고, 흐린 글자는 어긋남이 먼저 나서 보지도 않은 자리입니다. 위 줄에서도 창 밖의 흐린 글자는 그 창에서 읽지 않은 본문입니다.
사용 방법
- 1본문과 찾을 패턴을 넣습니다.
- 2「마지막 출현 표」에서 각 글자가 패턴의 어디에 마지막으로 나오는지 확인합니다.
- 3창을 대는 과정에서 파랗게 칠한 자리(어긋난 글자)와 미는 폭을 따라갑니다.
- 4아래 줄의 흐린 글자는 어긋남이 먼저 나서 보지도 않은 자리입니다.
- 5「읽지 않고 지나친 글자」가 본문의 몇 %인지로 건너뛰기가 얼마나 먹혔는지 봅니다.
자주 묻는 질문
글자를 아예 읽지 않고 건너뛸 수 있게 하려는 것입니다. 창의 맨 오른쪽에서 어긋났는데 그 자리의 본문 글자가 패턴에 아예 없다면 그 글자를 덮는 어떤 정렬도 답이 될 수 없으므로, 창을 패턴 길이만큼 통째로 밀 수 있고 지나친 글자는 한 번도 읽지 않습니다. 왼쪽부터 견주면 이런 판단을 할 수 없습니다.
어긋난 자리의 본문 글자를 패턴 안의 같은 글자에 맞춰 대라는 규칙입니다. 창의 j번째에서 어긋났고 그 본문 글자가 c라면 미는 폭은 max(1, j − last[c])이며, last[c]는 패턴 안에서 c가 마지막으로 나온 자리(없으면 −1)입니다. max로 1을 씌우는 이유는 last[c]가 j보다 오른쪽이면 값이 음수가 되어 창이 뒤로 가 버리기 때문이며, 이 max를 빼먹는 것이 구현의 1순위 실수입니다.
표를 하나 더 만들어야 해서 과정을 화면에 다 담기 어렵기 때문입니다. 원래의 보이어-무어는 나쁜 문자와 착한 접미사 두 규칙 중 더 많이 미는 쪽을 골라 최악의 경우도 O(n)이 됩니다. 나쁜 문자 규칙만 남긴 변형(호스풀)도 실전에서 널리 쓰이며, grep 계열이 쓰는 것도 대개 이쪽입니다.
아닙니다. 나쁜 문자 규칙만 쓰면 최악의 경우 O(nm)로, 단순 대조보다도 느려질 수 있습니다. 「AAAA…」에서 「BAAA」를 찾는 경우가 그렇습니다. 오른쪽 세 글자가 매번 맞고 맨 왼쪽에서만 어긋나는데, 나쁜 문자 A가 패턴 안에서 어긋난 자리보다 오른쪽에 있어 한 칸밖에 못 밉니다. 창마다 네 번씩 견주고 한 칸씩 미는 셈입니다.
KMP는 본문의 모든 글자를 적어도 한 번은 읽지만 보이어-무어는 읽지 않고 지나칠 수 있습니다. KMP는 최악의 경우가 O(n+m)으로 보장되는 대신 건너뛰기가 없고, 보이어-무어는 보장이 약한 대신 패턴이 길고 글자 종류가 많은 자료에서 훨씬 빠릅니다. 이 계산기의 비교 횟수는 kmp-failure·rabin-karp와 같은 기준으로 세므로 세 도구의 숫자를 그대로 견줄 수 있습니다.
건너뛸 수 있는 자료에서는 그렇습니다. 패턴에 없는 글자를 만나면 패턴 길이만큼 밀 수 있으므로, 패턴이 길수록 한 번에 더 많이 건너뜁니다. 「패턴이 길수록 빠르다」 예제에서 짧은 패턴과 긴 패턴의 비교 횟수를 견주면 긴 쪽이 더 적은 것을 볼 수 있습니다. 다만 위 최악의 경우처럼 매번 오른쪽이 맞아 버리는 자료에서는 반대가 됩니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 무작위 본문·패턴 3,000벌을 돌려 찾은 자리가 단순 대조의 답과 모두 일치하는지 대조해 했습니다. 겹치는 일치, 패턴이 본문보다 긴 경우, 빈 패턴도 함께 맞췄습니다.
- 「XXXX…」에서 다섯 글자 패턴을 찾으면 창마다 한 번만 견주고 다섯 칸씩 밀어 본문 100글자 중 80글자를 읽지 않는 것을 테스트로 고정해 두었습니다.
- 「AAAA…」에서 「BAAA」를 찾는 최악의 경우에 창마다 네 번씩 견주고 한 칸씩 미는 것, 그래서 단순 대조보다 비교가 많아지는 것도 테스트로 고정했습니다.
- 미는 폭이 항상 1 이상이라 창이 뒤로 가지 않는지 무작위 입력 1,000벌로 확인했습니다.
- 나쁜 문자 규칙만 씁니다. 착한 접미사 규칙을 함께 써야 최악의 경우가 O(n)이 되며, 여기서는 O(nm)로 남습니다.
- 비교 횟수는 「본문 한 글자 vs 패턴 한 글자」를 1회로 셉니다. kmp-failure·rabin-karp와 같은 기준입니다.
- 본문 400글자, 패턴 60글자까지 다룹니다. 창 30개까지만 그림으로 보이고, 그보다 많으면 실제 창 수를 따로 적습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.