|Author:||A. Klenin||Time limit:||2 sec|
|Input file:||input.txt||Memory limit:||200 Mb|
Many databases store the data in the character fields (and especially indices) using
prefix compression. This technique compresses a sequence of strings
A1, ..., AN by
the following method: if there are strings
Ai + 1 =
such that for some j ≤ min(p, q) ai,1 = ai+1,1, ai,2 = ai+1,2, ... ai,j = ai+1,j, then the second string is stored as [j]ai+1,j+1ai+1,j+2... ai+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.
|No.||Input file (
||Output file (|