Day 030-Q4 — Suffix Array + LCP（最長共通部分文字列）

問題

$K$ 個の文字列すべてに共通する最長部分文字列の長さを求めよ。

制約

入出力例

3
abcabc
bcdef
bcabc

2

bc が全文字列に共通の最長。

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from bisect import bisect_left
input = sys.stdin.readline

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

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

def solve():
    K = int(input())
    strings = [input().strip() for _ in range(K)]
    sep_base = 1
    T = ""
    starts = []
    for i, s in enumerate(strings):
        starts.append(len(T))
        T += s + chr(sep_base + i)
    n = len(T)
    sa = build_suffix_array(T)
    lcp = build_lcp_array(T, sa)
    def get_belong(pos):
        idx = bisect_left(starts, pos + 1) - 1
        return idx
    belong_sa = [get_belong(sa[i]) for i in range(n)]
    valid = [ord(T[sa[i]]) >= 97 for i in range(n)]

    def check(L):
        if L == 0:
            return True
        cnt = {}
        lo = 0
        for hi in range(n):
            if not valid[hi]:
                cnt = {}
                lo = hi + 1
                continue
            b = belong_sa[hi]
            cnt[b] = cnt.get(b, 0) + 1
            while lo < hi:
                if not valid[lo]:
                    lo += 1
                    cnt = {}
                    for j in range(lo, hi + 1):
                        if valid[j]:
                            cnt[belong_sa[j]] = cnt.get(belong_sa[j], 0) + 1
                    break
                if lcp[lo + 1] < L:
                    b_lo = belong_sa[lo]
                    cnt[b_lo] -= 1
                    if cnt[b_lo] == 0:
                        del cnt[b_lo]
                    lo += 1
                else:
                    break
            if len(cnt) == K:
                return True
        return False

    lo, hi = 0, min(len(s) for s in strings)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• K 個中 M 個以上に含まれる最長 substring
• Z-algorithm や Aho-Corasick との組合せ

自己評価

自分の回答

気づき・メモ