/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の文字列 S_1,S_2,\ldots,S_N が与えられます。
これらの文字列全てを部分文字列として含むような文字列の長さの最小値を求めてください。
ただし、ある文字列 S,T に対して、S が T を部分文字列として含むとは、S の先頭から 0 文字以上、末尾から 0 文字以上削除することで T が得られることをいいます。
制約
- N は整数
- 1\leq N \leq 20
- S_i は英小文字からなる長さ 1 以上の文字列
- S_1,S_2,\dots,S_N の長さの総和は 2\times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
3 snuke kensho uk
出力例 1
9
長さ 9 の文字列 snukensho は S_1,S_2,S_3 全てを部分文字列として含みます。
具体的には、snukensho の 1 文字目から 5 文字目までが S_1 に、4 文字目から 9 文字目までが S_2 に、3 文字目から 4 文字目までが S_3 にそれぞれ対応しています。
これより短い文字列であって、S_1,S_2,S_3 全てを部分文字列として含むものは存在しません。 よって、答えは 9 です。
入力例 2
3 abc abc arc
出力例 2
6
入力例 3
6 cmcmrcc rmrrrmr mrccm mmcr rmmrmrcc ccmcrcmcm
出力例 3
27
Score: 600 points
Problem Statement
You are given N strings S_1, S_2, \ldots, S_N.
Find the minimum length of a string that contains all these strings as substrings.
Here, a string S contains a string T as a substring if T can be obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
Constraints
- N is an integer.
- 1 \leq N \leq 20
- S_i is a string consisting of lowercase English letters whose length is at least 1.
- The total length of S_1, S_2, \dots, S_N is at most 2\times 10^5.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
3 snuke kensho uk
Sample Output 1
9
The string snukensho of length 9 contains all of S_1, S_2, and S_3 as substrings.
Specifically, the first to fifth characters of snukensho correspond to S_1, the fourth to ninth correspond to S_2, and the third to fourth correspond to S_3.
No shorter string contains all of S_1, S_2, and S_3 as substrings. Thus, the answer is 9.
Sample Input 2
3 abc abc arc
Sample Output 2
6
Sample Input 3
6 cmcmrcc rmrrrmr mrccm mmcr rmmrmrcc ccmcrcmcm
Sample Output 3
27