ABC287 E問題 Karuta

atcoder.jp

LCP ( = Longest Common Prefix, 最長共通接頭辞)

N 個の文字列が与えられます。その中の一つの文字列に選び、他の N-1個の文字列と比べます。その中で先頭から一致する文字数が最大になるケースを見つけることが求められています。

先頭から一致する文字数が最大になる相手を探すには、文字列を辞書順に並べて、注目している文字列の前後の文字列と比較すればよいです。

コード例 (Julia)

function solve()

  # 入力
  readInt()  =  parse(Int,readline())

  # 入力データ
  N = readInt()

  # タプル型の配列に (i,S[i]) の組を追加する
  T = Vector{Tuple{Int,String}}(undef,N)
  for i = 1:N
    S = readline()
    T[i] = (i,S)
  end

  # 文字列の辞書順に並び替える
  sort!(T, by = x -> x[2])

  # 答え配列 (初期値 0)
  ans = zeros(Int,N)

  # 辞書順に並んでいる文字列の隣同士の LCP の長さを調べる
  for i = 1:N-1
    N1,S1 = T[i]
    N2,S2 = T[i+1]
    L = min(length(S1),length(S2))
    LCP=L
    for j = 1:L
      if S1[j] != S2[j]
        LCP = j-1
        break
      end
    end

    # 最大の値を記録する
    ans[N1] = max(ans[N1],LCP)
    ans[N2] = max(ans[N2],LCP)
  end

  # 答え出力
  for i = 1:N
    println(ans[i])
  end

end  # function solve


# main
solve()