/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、文化祭の装飾として複数の看板を横一列につなげて長い横断幕を作ろうとしています。手元には N 枚の看板があり、i 番目の看板には文字列 S_i が書かれています。ここで、文字列 S_i の長さ（文字数）を |S_i| と表します。
高橋君はこれらの看板を 1 番目から N 番目まで順番に、左から右へつなげていきます。つなげるとき、スペースを節約するために、隣り合う 2 枚の看板同士をできるだけ多く重ねて配置します。
具体的には、i 番目の看板 (i \geq 2) をつなげるとき、直前の看板の文字列 S_{i-1} と今回の看板の文字列 S_i について、次の条件をすべて満たす正の整数 l を考えます。
- 1 \leq l < |S_{i-1}| かつ l < |S_i| である。（すなわち、どちらの文字列も完全には重なりに含まれず、それぞれ少なくとも 1 文字は重なりの外に残る。）
- S_{i-1} の末尾 l 文字と S_i の先頭 l 文字が一致する。
このような正の整数 l が存在する場合、その最大値を L_i とします。存在しない場合は L_i = 0 とします。
i 番目の看板をつなげる際、S_i の先頭 L_i 文字を直前の看板の末尾と重ねて配置します。L_i = 0 のときは重ねずにそのまま末尾に連結します。いずれの場合も、S_i のうち横断幕に新たに加わる文字数は |S_i| - L_i です。
N 枚すべての看板を順につなげたとき、横断幕全体の総文字数（重なった部分は一度だけ数える）を求めてください。
総文字数は次の式で計算できます。
|S_1| + \sum_{i=2}^{N} (|S_i| - L_i)
例
S_1 = abcabc、S_2 = abcxyz の場合を考えます。
S_1 の末尾と S_2 の先頭の一致を調べます。l の条件より 1 \leq l < 6 です。l = 3 のとき、S_1 の末尾 3 文字 abc と S_2 の先頭 3 文字 abc が一致します。l = 4, 5 では一致しません。よって条件を満たす最大の l は 3 であり、L_2 = 3 となります。
つなげた結果は abcabcxyz で、総文字数は 6 + (6 - 3) = 9 です。
制約
- 1 \leq N \leq 10^5
- 1 \leq |S_i| \leq 10^6
- \displaystyle \sum_{i=1}^{N} |S_i| \leq 10^6
- S_i は英小文字のみからなる。
入力
N S_1 S_2 \vdots S_N
1 行目には、看板の枚数を表す整数 N が与えられる。続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の看板に書かれた文字列 S_i が与えられる。
出力
N 枚の看板を順につなげたとき、横断幕全体の総文字数を整数として 1 行で出力せよ。
入力例 1
3 abcabc abcxyz xyzabc
出力例 1
12
入力例 2
4 cat dog bird fish
出力例 2
14
入力例 3
8 abracadabra abraxyz xyzxyz yzalpha alphabet betamax maximum umami
出力例 3
36
入力例 4
20 aaaaab abaaaa aaaacaaa caaad aadbbb bbbccc cccdde ddefgh ghijklm klmnop opqrstu stuvwx vwxyzab zabzab abzabc abcabcabc bcabcx xcdef defdefg fghello
出力例 4
71
入力例 5
1 a
出力例 5
1
Score : 433 pts
Problem Statement
Takahashi is trying to create a long banner by connecting multiple signs in a horizontal row as decoration for a cultural festival. He has N signs, and the i-th sign has the string S_i written on it. Here, the length (number of characters) of string S_i is denoted as |S_i|.
Takahashi connects these signs in order from the 1-st to the N-th, from left to right. When connecting them, to save space, he overlaps adjacent signs as much as possible.
Specifically, when connecting the i-th sign (i \geq 2), he considers positive integers l that satisfy all of the following conditions regarding the string S_{i-1} of the previous sign and the string S_i of the current sign:
- 1 \leq l < |S_{i-1}| and l < |S_i|. (That is, neither string is completely contained in the overlap, and each has at least 1 character remaining outside the overlap.)
- The last l characters of S_{i-1} match the first l characters of S_i.
If such a positive integer l exists, let L_i be its maximum value. If none exists, let L_i = 0.
When connecting the i-th sign, the first L_i characters of S_i are overlapped with the end of the previous sign. When L_i = 0, it is simply concatenated to the end without any overlap. In either case, the number of characters newly added to the banner from S_i is |S_i| - L_i.
Find the total number of characters of the entire banner when all N signs are connected in order (where overlapping portions are counted only once).
The total number of characters can be calculated by the following formula:
|S_1| + \sum_{i=2}^{N} (|S_i| - L_i)
Example
Consider the case where S_1 = abcabc and S_2 = abcxyz.
We check for matches between the suffix of S_1 and the prefix of S_2. By the condition on l, we have 1 \leq l < 6. When l = 3, the last 3 characters of S_1, abc, match the first 3 characters of S_2, abc. For l = 4, 5, there is no match. Therefore, the maximum l satisfying the conditions is 3, and L_2 = 3.
The connected result is abcabcxyz, and the total number of characters is 6 + (6 - 3) = 9.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq |S_i| \leq 10^6
- \displaystyle \sum_{i=1}^{N} |S_i| \leq 10^6
- S_i consists only of lowercase English letters.
Input
N S_1 S_2 \vdots S_N
The first line contains an integer N representing the number of signs. In the following N lines, the i-th line (1 \leq i \leq N) contains the string S_i written on the i-th sign.
Output
Output in a single line the total number of characters of the entire banner when the N signs are connected in order, as an integer.
Sample Input 1
3 abcabc abcxyz xyzabc
Sample Output 1
12
Sample Input 2
4 cat dog bird fish
Sample Output 2
14
Sample Input 3
8 abracadabra abraxyz xyzxyz yzalpha alphabet betamax maximum umami
Sample Output 3
36
Sample Input 4
20 aaaaab abaaaa aaaacaaa caaad aadbbb bbbccc cccdde ddefgh ghijklm klmnop opqrstu stuvwx vwxyzab zabzab abzabc abcabcabc bcabcx xcdef defdefg fghello
Sample Output 4
71
Sample Input 5
1 a
Sample Output 5
1