AtCoder ABC058 C - 怪文書

概要

• n個の文字列sが与えられる
• 最長の文字列saを求めよ。この文字列はすべてのsに含まれる文字列だけで構成されている。
• この文字列は考えられる文字列の中の辞書順で一番小さなものである。

アプローチ1: aから各文字列の個数をカウントし、正解を表示

cbaa ⇒ a*2, b*1, c*1, d*0
daacc ⇒ a*2, b*0, c*2, d*1
acacac ⇒ a*3, b * 0, c*3, d*0

であるから、各文字について最小の個数を取ると、a * 2, b*0, c*1, d*0となり、これを実装すればよい。

s = ""
dat = []
n = int(input())
for _ in range(n):
    dat.append(input())
for i in range(26):
    tch = chr(ord("a") + i)
    num = 99999
    for j in range(len(dat)):
        num = min(num, dat[j].count(tch))
    s += tch * num
print(s)

アプローチ2: LCS

各文字列をsortして、順番にLCSをとる。つまり、

cbaa ⇒ aabc
daacc ⇒ aaccd
acacac ⇒ aaaccc

であるから、まず、1,2個目でLCMをとるとaacになり、この結果と3個目のLCSをとるとaacが得られる。
ライブラリがあるならこの方が早いかも。

# アルゴリズムイントロダクション 15.4 LCS
# Longest Common Subsequenceをとり、以下を返す
# b: 結果
# c: そこまでのlongestのcount(内部用)
def lcs_length(x, y):
    m, n = len(x), len(y)
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = '↖'
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
                b[i][j] = "↑"
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = "←"
    return c, b
 
# アルゴリズムイントロダクション 15.4 LCS
# bを基にもともとのinput xから共通部分を抜き出す。
def lcs_decode(b, X, i, j):
    import collections
    res = collections.deque([])
    while True:
        # print("i={0}, j={1} b={2}".format(i,j,b[i][j]))
        if i == 0 or j == 0:
            break
        if b[i][j] == '↖':
            res.appendleft(X[i - 1])
            i -= 1
            j -= 1
        elif b[i][j] == "↑":
            i -= 1
            continue
        else:
            j -= 1
            continue
    return res 
n = int(input())
dat = []
for _ in range(n):
    s = input()
    s = "".join(sorted(list(s)))
    dat.append(s)
cs = dat[0]
for i in range(1, n):
    c, b = lcs_length(cs, dat[i])
    cs = "".join(lcs_decode(b, cs, len(cs), len(dat[i])))
print(cs)