Day 097-Q4 | Suffix Automaton拡張（複数文字列共通部分文字列）

問題

$K$ 個の文字列 $s_1,\dots,s_K$（英小文字のみ）が与えられる。すべての $s_1,\dots,s_K$ に部分文字列として登場する、空でない文字列の種類数を求めよ。

入力形式

K
s_1
:
s_K

制約

$1 \le K \le 8$

$1 \le |s_i| \le 300$

$s_i$ は英小文字のみ

入出力例

入力例1

2
abc
bca

出力例1

abcの部分文字列: a,b,c,ab,bc,abc。bcaの部分文字列: b,c,a,bc,ca,bca。共通するのは a,b,c,bc の4種類。

概念図

ヒント（段階的開示）

ヒント1: 方向性

1つの文字列の異なる部分文字列を数えるだけなら通常の Suffix Automaton（SAM）を1本作ればよい。$K$ 個すべてに共通する部分文字列を数えるには、各状態が「どの文字列由来の出現を含んでいるか」を管理できないかを考えよ。

ヒント2: アプローチ

各文字列の間に他のどの文字列にも現れない一意な区切り文字を挟んで連結した $T$ を作り、$T$ 全体に対して普通のSAMを構築する。各文字を追加した直後の状態に owner ビットを記録し、suffix link 木を葉から根へ（length降順で）ビットをOR伝播させれば、各状態の「出現する文字列集合」が求まる。

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

order = sorted(range(1, n_states), key=lambda x: -length[x])
for v in order:
    p = link[v]
    if p != -1:
        mask[p] |= mask[v]

full = (1 << K) - 1
ans = sum(length[v] - length[link[v]] for v in range(1, n_states) if mask[v] == full)

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split('\n')
    idx = 0
    K = int(data[idx]); idx += 1
    strings = []
    for _ in range(K):
        strings.append(data[idx]); idx += 1

    SEP_BASE = 200
    T = []
    owner = []
    for i, s in enumerate(strings):
        for ch in s:
            T.append(ch)
            owner.append(i)
        T.append(chr(SEP_BASE + i))
        owner.append(-1)

    link = [-1]
    length = [0]
    trans = [dict()]
    mask = [0]
    last = 0

    def sa_extend(c, owner_idx):
        nonlocal last
        cur = len(length)
        length.append(length[last] + 1)
        link.append(-1)
        trans.append(dict())
        mask.append(0 if owner_idx < 0 else (1 << owner_idx))

        p = last
        while p != -1 and c not in trans[p]:
            trans[p][c] = cur
            p = link[p]
        if p == -1:
            link[cur] = 0
        else:
            q = trans[p][c]
            if length[q] == length[p] + 1:
                link[cur] = q
            else:
                clone = len(length)
                length.append(length[p] + 1)
                link.append(link[q])
                trans.append(dict(trans[q]))
                mask.append(0)
                while p != -1 and trans[p].get(c) == q:
                    trans[p][c] = clone
                    p = link[p]
                link[q] = clone
                link[cur] = clone
        last = cur

    for pos, c in enumerate(T):
        sa_extend(c, owner[pos])

    n_states = len(length)
    order = sorted(range(1, n_states), key=lambda x: -length[x])
    for v in order:
        p = link[v]
        if p != -1:
            mask[p] |= mask[v]

    full = (1 << K) - 1
    ans = 0
    for v in range(1, n_states):
        if mask[v] == full:
            ans += length[v] - length[link[v]]

    print(ans)


solve()

計算量: $|T|=\sum|s_i|+K$ として SAM構築 $O(|T|\log\sigma)$、mask伝播 $O(|T|)$。全体 $O(|T|\log|T|)$ 程度。

Step-by-Step 解説

1一意な区切り文字での連結
他のどの文字列にも現れない専用の区切り文字を挟んで1本の文字列 $T$ に連結する。

2通常のSAM構築
$T$ を先頭から1文字ずつ追加する教科書通りの単一文字列SAM構築をそのまま使う。

3出現元ビットマスクの記録と伝播
各文字追加直後の last にownerビットを立て、length降順で親にOR伝播させる。

4集計
mask[v]==full の状態について length[v]-length[link[v]] を合計する。

よくあるミス

ミス	原因	正しい書き方
区切り文字が元のアルファベットと衝突	区切り文字コードを適当に選ぶ	英小文字の範囲(97-122)と重ならないコードを使う
区切り文字自身にも文字列ビットを立ててしまう	ownerの設定を誤る	区切り文字のownerは-1とし、maskに何も立てない
maskの伝播順序をlength昇順にする	子→親の向きを逆にする	必ずlengthの降順で処理する
clone状態のmask初期値を親と同じにする	cloneは出現位置を持たない補助状態	cloneのmaskは必ず0で初期化する

次のステップ

発展: 「K個中t個以上の文字列に共通」の数え上げ（popcount判定）への一般化
発展: 一般化Suffix Automaton（文字列ごとにlastをリセットする方式）との実装比較
次回予告: 次数制約部分グラフ（b-マッチング・最大流帰着）

自己評価

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

Day 097-Q4 — Suffix Automaton拡張（複数文字列連結・全文字列共通部分文字列数え上げ）

問題