Day 100-Q2 | Boyer-Moore法（文字列探索）

問題

文字列 $T$（長さ $N$）の中から、パターン文字列 $P$（長さ $M$）が出現するすべての位置を求めよ。位置は $0$-indexed とし、$T[i:i+M]=P$ となる $i$ をすべて昇順に列挙する。

Boyer-Moore法は $P$ の末尾から照合し、不一致時に「Bad Character則」と「Good Suffix則」の両方を使ってスキップ幅を決めることで、実用上非常に高速な検索を実現する。両ルールを実装し、探索せよ。

入力形式

T
P

制約

$1 \le M \le N \le 5\times10^5$

$T, P$ は英小文字のみ

入出力例

入力例1

abracadabra
abra

出力例1

2
0 7

出現数が0の場合、2行目は空行を出力すればよい。

概念図

ヒント（段階的開示）

ヒント1: 方向性

KMP法は一致した部分の情報を使ってずらすが、Boyer-Moore法はさらに「不一致になった1文字」の情報も使う。パターンを末尾から照合するのはなぜか（不一致文字より右側の情報を使える）を考えよ。

ヒント2: アプローチ

1. Bad Character則: テキスト側の不一致文字の、パターン内での最後の出現位置を使ってシフト量を決める。

2. Good Suffix則: 不一致より右側ですでに一致していた接尾辞が、パターン内の別の場所に再び現れる位置までシフトする（境界配列を反転Z-algorithm相当で構築）。

実際のシフト幅は両者の大きい方を採用する。

ヒント3: 誘導（コード骨格）

shift = [0] * (m + 1)
border_pos = [0] * (m + 1)
i, j = m, m + 1
border_pos[i] = j
while i > 0:
    while j <= m and pat[i - 1] != pat[j - 1]:
        if shift[j] == 0:
            shift[j] = j - i
        j = border_pos[j]
    i -= 1; j -= 1
    border_pos[i] = j
j = border_pos[0]
for i in range(m + 1):
    if shift[i] == 0:
        shift[i] = j
    if i == j:
        j = border_pos[j]

探索本体: 末尾から照合→全一致ならshift[0]分進める→不一致ならmax(bad,good,1)分進める。

模範解答 (Python)

import sys


def build_bad_char(pat):
    last = {}
    for i, c in enumerate(pat):
        last[c] = i
    return last


def build_good_suffix(pat):
    m = len(pat)
    shift = [0] * (m + 1)
    border_pos = [0] * (m + 1)
    i, j = m, m + 1
    border_pos[i] = j
    while i > 0:
        while j <= m and pat[i - 1] != pat[j - 1]:
            if shift[j] == 0:
                shift[j] = j - i
            j = border_pos[j]
        i -= 1
        j -= 1
        border_pos[i] = j
    j = border_pos[0]
    for i in range(m + 1):
        if shift[i] == 0:
            shift[i] = j
        if i == j:
            j = border_pos[j]
    return shift


def boyer_moore_search(text, pat):
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    bad_char = build_bad_char(pat)
    good_suffix = build_good_suffix(pat)
    res = []
    s = 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pat[j] == text[s + j]:
            j -= 1
        if j < 0:
            res.append(s)
            s += good_suffix[0]
        else:
            bc_shift = j - bad_char.get(text[s + j], -1)
            gs_shift = good_suffix[j + 1]
            s += max(bc_shift, gs_shift, 1)
    return res


def solve():
    text = input().strip()
    pat = input().strip()
    res = boyer_moore_search(text, pat)
    print(len(res))
    print(*res)


solve()

計算量: 前処理 $O(M)$、探索は実用上非常に高速（悪化すると $O(NM)$、Galil則を足せば最悪 $O(N+M)$）。

Step-by-Step 解説

1Bad Character表の構築
パターン内で各文字が最後に出現する位置を$O(M)$で記録する。

2Good Suffix表の構築
反転Z-algorithm相当の処理で境界配列を$O(M)$で計算する。

3末尾からの照合
j=m-1から一致を確認し、全一致なら出現位置として記録する。

4シフト幅の決定
両ルールのシフト量の大きい方を採用する（正当性は保たれる）。

5計算量の直感
実務上は高速。真に最悪$O(N+M)$を保証するにはGalil則が必要。

よくあるミス

ミス	原因	正しい書き方
Good Suffix則を省略しBad Characterのみ実装	Boyer-Moore-Horspool法との混同	周期的文字列で劣化するため両ルールを実装する
マッチ成功時に常に1文字だけ進める	Good Suffix表の`shift[0]`の意味の理解不足	マッチ時は`shift[0]`を使い重複マッチを効率よく探す
境界配列の添字を1つずらしてバグる	0-indexedと1-indexed的な扱いが混在	`shift[j]`の意味（不一致がj文字目より右で起きた時のシフト量）を明確化
Bad Character則のシフトが負になるのを見落とす	不一致文字の最後の出現がより右側にある場合	`max(bc_shift, gs_shift, 1)`で最低1文字は進める

次のステップ

発展: Galil則を追加し最悪計算量を真に$O(N+M)$に保証する
複数パターン同時検索にはAho-Corasick法の方が適している点を比較する
次回予告: DC3法／Skew Algorithm（Suffix Arrayの線形時間構築）

自己評価

完全理解おおむね理解要復習

Day 100-Q2 — Boyer-Moore法（文字列探索）

問題