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()