Day 083-Q1 — Suffix Automaton + 最長共通部分文字列クエリ（SA-DAWG・LCS $O(N+M)$）

問題

文字列 $S$（長さ $N$）が与えられる。$Q$ 個のクエリが与えられ、各クエリでは文字列 $T_i$（長さ $M_i$）が与えられる。各クエリについて $S$ と $T_i$ の最長共通部分文字列（LCS）の長さを求めよ。

Suffix Automaton を $S$ に対して $O(N)$ で構築し、各 $T_i$ を SAM 上で走査することで $O(N + \sum M_i)$ で全クエリに答えよ。

入出力例

7 3
abcabcd
3
abc
4
abcd
5
xyzab

3
4
2

概念図: Suffix Automaton の構造と LCS クエリ

ヒント

def lcs_query(T):
    cur, cur_len, ans = 0, 0, 0
    for c in T:
        while cur != 0 and c not in sa_trans[cur]:
            cur = sa_link[cur]
            cur_len = sa_len[cur]  # suffix link 先の len に制限
        if c in sa_trans[cur]:
            cur = sa_trans[cur][c]
            cur_len += 1
        ans = max(ans, cur_len)
    return ans

模範解答

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    S = input().strip()

    MAXN = 2 * N + 5
    sa_len = [0] * MAXN
    sa_link = [-1] * MAXN
    sa_trans = [None] * MAXN
    for i in range(MAXN):
        sa_trans[i] = {}

    size = 1
    last = 0

    def extend(c):
        nonlocal size, last
        cur = size; size += 1
        sa_len[cur] = sa_len[last] + 1
        p = last
        while p != -1 and c not in sa_trans[p]:
            sa_trans[p][c] = cur
            p = sa_link[p]
        if p == -1:
            sa_link[cur] = 0
        else:
            q = sa_trans[p][c]
            if sa_len[p] + 1 == sa_len[q]:
                sa_link[cur] = q
            else:
                clone = size; size += 1
                sa_len[clone] = sa_len[p] + 1
                sa_link[clone] = sa_link[q]
                sa_trans[clone] = dict(sa_trans[q])
                while p != -1 and sa_trans[p].get(c) == q:
                    sa_trans[p][c] = clone
                    p = sa_link[p]
                sa_link[q] = clone
                sa_link[cur] = clone
        last = cur

    for c in S:
        extend(c)

    results = []
    for _ in range(Q):
        M = int(input().strip())
        T = input().strip()
        cur = 0
        cur_len = 0
        ans = 0
        for c in T:
            while cur != 0 and c not in sa_trans[cur]:
                cur = sa_link[cur]
                cur_len = sa_len[cur]
            if c in sa_trans[cur]:
                cur = sa_trans[cur][c]
                cur_len += 1
            ans = max(ans, cur_len)
        results.append(ans)

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

Step 1: SAM の構造

SAM のノード数は最大 $2N-1$、辺数は最大 $3N-4$。

Step 2: extend 操作（$O(N)$ amortized）

新文字 $c$ を追加するたびに最大2ノードが生成される。cur: 新しい部分文字列を受理するノード。clone: 既存ノードの分割（suffix link 修正のため）。

clone = size; size += 1
sa_len[clone] = sa_len[p] + 1
sa_link[clone] = sa_link[q]
sa_trans[clone] = dict(sa_trans[q])  # 必ず浅いコピー

Step 3: LCS クエリ処理（$O(\sum M_i)$）

クエリ文字列 $T$ を SAM 上で走査。遷移できない場合は suffix link を辿って後退し、cur_len = sa_len[cur] に更新する。各ステップでの cur_len の最大値が LCS 長。

よくあるミス

次のステップ

• 発展問題: 複数の文字列 $S_1, \ldots, S_K$ の全ての LCS を求めよ（Generalized SAM）
• 参考: Blumer et al. (1985) "The smallest automaton recognizing the subwords of a text"

自己評価