Day 117-Q3 | 複数文字列の最長共通部分文字列（Generalized Suffix Array）

問題

$K$ 個の文字列 $S_1,\dots,S_K$（小文字英字のみ）が与えられる。全ての $S_i$ に共通して部分文字列として現れる文字列のうち、最も長いものの長さを求めよ。共通する部分文字列が存在しない場合は $0$ を出力せよ。

入力形式

K
S_1
S_2
:
S_K

制約

$2 \le K \le 10$

$1 \le |S_i|$

全文字列の長さの合計 $\le 500$

入出力例

入力例1

2
abab
aba

出力例1

入力例2

3
abcdef
zcdefg
xxcdeyy

出力例2

入力例1: "aba" が両方の文字列に部分文字列として現れ、これが最長。入力例2: "cde" が3文字列全てに共通する最長の部分文字列。入力例3 ("abc","def") の答えは0。

概念図: 接尾辞配列上のスライディングウィンドウ

ヒント（段階的開示）

ヒント1: 方向性

2つの文字列の最長共通部分文字列は、両方の文字列を連結して接尾辞配列を作り、隣接する接尾辞のLCP（最長共通接頭辞）を見ることで求められることが知られている。これを $K$個の文字列に一般化するには、各接尾辞に「どの文字列由来か」というラベルを付け、接尾辞配列上で $K$種類全てのラベルを含む区間を探す問題に帰着させる。

ヒント2: アプローチ

複数の文字列を、互いに異なる番兵文字で区切って1つの文字列に連結し、接尾辞配列とLCP配列（Kasaiのアルゴリズム）を構築する。接尾辞配列は辞書順にソートされているため、隣接する接尾辞同士のLCPの最小値が、その区間内の任意の2接尾辞の共通接頭辞長に一致するという性質を利用する。「$K$種類のラベル全てを含む最小の連続区間」をスライディングウィンドウで探索し、その区間内のLCPの最小値の最大値を答えとする。

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

# 1. 各文字列の末尾に固有の番兵（他のどの文字とも被らない値）を付けて連結
# 2. 連結した列の接尾辞配列 sa と LCP配列 lcp（Kasai法）を構築
# 3. sa[i] が元々どの文字列に属するかを示す label 配列を作る（番兵はラベル-1）
# 4. 接尾辞配列上を左端 l から右端 r へスライドさせ、
#    区間 [l, r] に K 種類のラベルが揃った時点の
#    「区間内の隣接LCPの最小値」の最大値を答えとする

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    k = int(data[0])
    strings = data[1:1 + k]

    seq = []
    label = []
    for i, s in enumerate(strings):
        for ch in s:
            seq.append(ord(ch))
            label.append(i)
        seq.append(-(i + 1))  # 文字列ごとに異なる番兵
        label.append(-1)

    n = len(seq)
    sa = sorted(range(n), key=lambda i: seq[i:])

    rank = [0] * n
    for i, s in enumerate(sa):
        rank[s] = i
    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 seq[i + h] == seq[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
        else:
            h = 0

    labels_sorted = [label[sa[i]] for i in range(n)]
    ans = 0
    for l in range(n):
        seen = set()
        if labels_sorted[l] != -1:
            seen.add(labels_sorted[l])
        cur_min = None
        for r in range(l + 1, n):
            cur_min = lcp[r] if cur_min is None else min(cur_min, lcp[r])
            if labels_sorted[r] != -1:
                seen.add(labels_sorted[r])
            if len(seen) == k:
                if cur_min > ans:
                    ans = cur_min
                break

    print(ans)


solve()

計算量: 接尾辞配列の構築は単純比較ソートで $O(N^2\log N)$（$N\le510$程度なら十分高速）。Kasai法によるLCP配列構築は $O(N)$。大規模な $N$ を扱う場合は SA-IS 法で $O(N)$ 構築＋尺取り法が必要。入力例1〜3で検証済み。

Step-by-Step 解説

1番兵付き連結
各文字列の末尾に、他のどの文字列とも異なる固有の番兵（負の整数）を挿入して1つの列に連結する。番兵を通常の文字より小さい値にすることで、文字列をまたいだ誤った一致が起きない。

2接尾辞配列とLCP配列
連結した列の全ての接尾辞を辞書順にソートしたものが接尾辞配列。隣り合う接尾辞同士の最長共通接頭辞の長さを記録したものがLCP配列で、Kasaiのアルゴリズムにより $O(N)$ で計算できる。

3「区間内のLCPの最小値」性質
接尾辞配列上で連続した区間 $[l,r]$ を取ったとき、区間に含まれる任意の2接尾辞の共通接頭辞の長さは、区間内の隣接LCPの最小値に一致する。

4スライディングウィンドウで$K$種類を揃える
左端 $l$ を固定し右端 $r$ を伸ばしながら、ラベルの種類数が $K$ に達した時点で打ち切る。$r$をさらに伸ばしても最小値は単調非増加なので、この時点の値がこの$l$にとっての最良値。

5番兵ラベル(-1)の扱い
番兵の位置はseen集合には加えないが、LCP値の計算対象からは除外しない（番兵をまたぐと自然にLCPが0になり、正しく区切りとして機能する）。

よくあるミス

ミス	原因	正しい書き方
全ての文字列に同じ番兵文字を使ってしまう	番兵は「区切り」であればどれも同じでよいと誤解する	番兵は文字列ごとに異なる値にする
ラベルが揃った時点で打ち切らず全区間を試してしまう	「区間を伸ばすと最小値は単調非増加」という性質を見落とす	$K$種類揃った時点で即座に`break`してよい
2文字列版のDPをそのまま複数文字列に拡張しようとする	文字列数$K$が増えるとDPの次元が指数的に増える	接尾辞配列＋ラベル管理なら$K$に対して線形にスケールする
番兵を通常の文字コードより大きい値にしてしまう	「番兵は特別な値であればどこでもよい」と誤解する	番兵は必ず通常の文字より小さい値にする

Day 117-Q3 — 複数文字列の最長共通部分文字列（Generalized Suffix Array）

問題