Day 108-Q4 — 複数文字列の最長共通部分文字列

問題

$K$個の文字列$s_1, s_2, \ldots, s_K$（すべて小文字英字のみ）が与えられる。すべての$s_i$に共通して部分文字列として現れる文字列のうち、最長のものの長さを求めよ（そのような文字列が存在すれば、実際に1つ具体例を出力せよ）。

一般化Suffix Array（全文字列を区切り文字で連結したSuffix Array）とLCP配列を構築し、Suffix Array順に並んだ接尾辞列の上をスライディングウィンドウで走査することで、$O(N\log N)$（$N$は全文字列の合計長）で解け。

入力形式

K
s_1
s_2
...
s_K

制約

入出力例

3
xabcyz
bcxxab
zzabcw

2
ab

"ab"は3つの文字列すべてに部分文字列として現れる。"abc"はbcxxabに含まれないため不可。長さ3以上の共通部分文字列は存在しない。出力の具体例は複数正解がありうる（"bc"も長さ2の別解）。

2
apple
banana

1
a

概念図: SA順に並んだ接尾辞の上を尺取り

ヒント（段階的開示）

# S = s_1 + sep_1 + s_2 + sep_2 + ... + s_K + sep_K  （sep_iは互いに異なるユニークな文字）
# tag[i] = 元の文字列インデックス（区切り文字の位置は -1）
# sa, rank = build_sa(S); lcp = build_lcp(S, sa, rank)
# sa_tag[i] = tag[sa[i]]  # SA順に並べたタグ列

# 尺取り法: r を伸ばしてタグが K 種類揃うまで進め、
# 揃ったら l を縮めながら「区間内の隣接LCPの最小値」を単調キューで求め、その最大値を答えにする
# ウィンドウ [l, r] の有効なLCP区間は lcp[l+1 .. r]（インデックスl自体のlcpは範囲外）

模範解答 (Python)

📋 コピーimport sys
from collections import deque

def build_sa(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        def keyf(x):
            return (rank[x], rank[x + k] if x + k < n else -1)
        sa.sort(key=keyf)
        tmp = [0] * n
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if keyf(sa[i - 1]) < keyf(sa[i]) else 0)
        rank = tmp
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa, rank

def build_lcp(s, sa, rank):
    n = len(s)
    lcp = [0] * n
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
        else:
            h = 0
    return lcp

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    K = int(data[idx]); idx += 1
    strs = []
    for _ in range(K):
        strs.append(data[idx].decode()); idx += 1

    S_parts = []
    tag = []
    for i, s in enumerate(strs):
        S_parts.append(s)
        tag.extend([i] * len(s))
        S_parts.append(chr(1 + i))  # 固有の区切り文字
        tag.append(-1)
    S = "".join(S_parts)

    sa, rank = build_sa(S)
    lcp = build_lcp(S, sa, rank)
    n = len(S)
    sa_tag = [tag[sa[i]] for i in range(n)]

    count = {}
    have = 0
    need = K
    dq = deque()

    ans = 0
    ans_range = (0, 0)
    l = 0
    for r in range(n):
        t = sa_tag[r]
        if t != -1:
            if count.get(t, 0) == 0:
                have += 1
            count[t] = count.get(t, 0) + 1
        if r > 0:
            while dq and lcp[dq[-1]] >= lcp[r]:
                dq.pop()
            dq.append(r)
        while have == need:
            cur = lcp[dq[0]] if dq else 0
            if cur > ans:
                ans = cur
                ans_range = (sa[l], sa[l] + cur)
            tl = sa_tag[l]
            if tl != -1:
                count[tl] -= 1
                if count[tl] == 0:
                    have -= 1
            l += 1
            while dq and dq[0] <= l:
                dq.popleft()

    out = [str(ans)]
    if ans > 0:
        out.append(S[ans_range[0]:ans_range[1]])
    print("\n".join(out))


solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 「$K$個中$t$個以上の文字列に共通して現れる最長部分文字列」に一般化する（タグの種類数条件をhave >= tに変える）
• 発展: Suffix Array構築をSA-IS法に置き換えて$O(N)$に高速化する
• 次回予告: 有理数復元（Rational Reconstruction・拡張ユークリッドによるmod pからの分数復元）

自己評価

自分の回答

気づき・メモ