Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Simple prefix compression
Description Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A1, ..., A _{N} by the following method: if there are strings Ai = a_{i,1}a_{i,2}...a_{i,p} and A_{i + 1} = a_{i+1,1}a_{i+1,2}...a_{i+1,q}
such that for some j ≤ min(p, q) a _{i,1} = a_{i+1,1}, a_{i,2} = a_{i+1,2}, ... a_{i,j} = a_{i+1,j}, then the second string is stored as [j]a_{i+1,j+1}a_{i+1,j+2}... a_{i+1,q}, where [j] is a single character with code j.
If j = 0, that is, strings do not have any common prefix, then the second string is prefixed with zero byte, and so the total length actually increases. Constraints
1 ≤ N ≤ 10000, 1 ≤ length(Ai) ≤ 255. Input First line of input contains integer number N, with following N lines containing strings A1 ... A _{N}Output Output must contain a single integer -- minimal total length of compressed strings. Sample Input 3 abc atest atext Sample Output 11 Source Northeastern Europe 2003, Far-Eastern Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator