Day 149-Q1 — FM-index（簡略版・BWT+rankによるバックワード検索パターンカウント）

2026-09-10 赤色 Master / Phase 8+ ★★★★★★★★★ BWT列とC[c]・Occ(c,i)だけで接尾辞配列を陽に使わずパターン出現回数を数える

問題

小文字英字と末尾1文字の $（他のどの文字よりも辞書順で小さい区切り文字）からなる文字列 S（長さn）が与えられる。以下の手順でFM-index（簡略版）を構築し、クエリ文字列 P それぞれについて S 中の P の出現回数を、愚直な文字列探索を使わず バックワード検索 のみで求めよ。

構築手順

  1. 全ての巡回シフトを辞書順ソートした開始位置列を接尾辞配列 SA とする。
  2. BWT[i] = S[(SA[i]-1) mod n]
  3. C[c] = S 中で c より真に小さい文字の総数。
  4. Occ(c, i) = BWT[0:i]（半開区間）中の c の出現回数。

バックワード検索（末尾の文字から処理）

lo, hi = 0, n
for ch in reversed(P):
    lo = C[ch] + Occ(ch, lo)
    hi = C[ch] + Occ(ch, hi)
    if lo >= hi:
        return 0
return hi - lo

入力形式

S
Q
P_1
:
P_Q

制約

$3 \le |S| \le 30$（$含む）
$1 \le Q \le 10$
各 $P_i$ は小文字英字のみ、$1 \le |P_i| \le 10$
$ は末尾に1文字だけ、他の文字より辞書順最小

入出力例

入力例1

banana$
5
ana
na
a
ban
xyz

出力例1

2
2
3
1
0

BWT(banana$) = "annb$aa"。C = {$:0, a:1, b:4, n:5}。これらだけで愚直探索なしに出現回数を求める。

概念図：バックワード検索によるレンジの絞り込み（クエリ "ana"）

S = banana$ (n=7) / BWT = a n n b $ a a 初期範囲 [lo,hi) = [0,7) 'a' を処理 → C[a]=1, Occ(a,0)=0, Occ(a,7)=3 → [1,4) 'n' を処理 → C[n]=5, Occ(n,1)=0, Occ(n,4)=2 → [5,7) 'a' を処理 → C[a]=1, Occ(a,5)=1, Occ(a,7)=3 → [2,4) 最終幅 hi-lo = 4-2 = 2 → "ana" の出現回数は 2 末尾の文字から処理するたび範囲が縮む。愚直探索なしに範囲の幅だけで出現回数が求まる

ヒント（段階的開示）

ヒント1（方向性）

BWTは「Sの全巡回シフトをソートしたときの各行の最後の文字」。ソート済み巡回シフトの並びは接尾辞配列の並びと本質的に同じなので、BWT[i]は「辞書順でi番目の接尾辞の直前の文字」を意味する。この性質からパターンの末尾の文字から1文字ずつ絞り込む探索ができる。

ヒント2（アプローチ）

C[c]は「cから始まる接尾辞の範囲がSAのどこから始まるか」を表す。Occ(c,i)と組み合わせると、候補範囲[lo,hi)の中で直前の文字がcである接尾辞だけに絞り込んだ新しい範囲をC[c]+Occ(c,lo)からC[c]+Occ(c,hi)として計算できる。

ヒント3（誘導） 
def build_fm(S):
    n = len(S)
    sa = sorted(range(n), key=lambda i: S[i:])
    bwt = ''.join(S[(i - 1) % n] for i in sa)
    chars = sorted(set(S))
    C, total = {}, 0
    for c in chars:
        C[c] = total
        total += bwt.count(c)
    return bwt, C

def occ(bwt, c, i):
    return bwt[:i].count(c)

模範解答 (Python)

import sys


def build_fm(S):
    n = len(S)
    sa = sorted(range(n), key=lambda i: S[i:])
    bwt = ''.join(S[(i - 1) % n] for i in sa)
    chars = sorted(set(S))
    C = {}
    total = 0
    for c in chars:
        C[c] = total
        total += bwt.count(c)
    return bwt, C


def occ(bwt, c, i):
    return bwt[:i].count(c)


def backward_count(S, P, bwt, C):
    n = len(S)
    lo, hi = 0, n
    for ch in reversed(P):
        if ch not in C:
            return 0
        lo = C[ch] + occ(bwt, ch, lo)
        hi = C[ch] + occ(bwt, ch, hi)
        if lo >= hi:
            return 0
    return hi - lo


def main():
    data = sys.stdin.read().split()
    S = data[0]
    Q = int(data[1])
    bwt, C = build_fm(S)
    out = []
    for i in range(Q):
        P = data[2 + i]
        out.append(str(backward_count(S, P, bwt, C)))
    print('\n'.join(out))


main()

Step-by-Step 解説

1BWTを構築する
全巡回シフトを辞書順ソートし、各行の最後の1文字を集める。$が最小文字なので通常の接尾辞配列と一致する。
2C[c]を求める
C[c]は「Sの中でcより辞書順で小さい文字が何個あるか」。cから始まる接尾辞ブロックがSAのどこから始まるかに一致する。
3Occ(c,i)の役割
候補範囲[lo,hi)の中で直前の文字がcの接尾辞はOcc(c,hi)-Occ(c,lo)個あり、全てC[c]+Occ(c,lo)から始まる範囲に移動する（LFマッピング）。
4末尾から先頭へ縮小
パターン全体を処理し終えた範囲の幅がそのまま出現回数になる。

よくあるミス

ミス原因正しい書き方
パターンを先頭から処理してしまう通常の文字列探索の感覚で先頭から読むバックワード検索は必ず末尾の文字から処理する
C[c]を「c以下の文字数」で計算境界条件の誤りC[c]はcより真に小さい文字の総数にする
lo>=hi後も処理を続ける早期終了の判定漏れ候補範囲が空になった時点で0を返す
Occをbwt[:i+1]で数える半開区間の境界を誤解Occ(c,i)はbwt[0:i]と統一する
Cに無い文字の扱いを忘れるSに出現しない文字を含むPの扱い漏れCに無い文字が来たら出現回数0で打ち切る

次のステップ

  • 発展: 本問ではOcc(c,i)を毎回$O(n)$で愚直に数えたが、実際のFM-indexでは各文字ごとのビットベクトルにRank/Select構造（Day145-Q3）を載せ$O(1)$に高速化する。
  • 次回予告: BK-tree（Burkhard-Keller Tree・編集距離の三角不等式による距離空間探索木）

自己評価

自分の回答

気づき・メモ