描述
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 = ai,1ai,2…ai,p and Ai + 1= ai+1,1ai+1,2…ai+1,q 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.
Constraints 1 <= N <= 10000, 1 <= length(Ai) <= 255. 输入 First line of input contains integer number N, with following N lines containing strings A1 … AN 输出 Output must contain a single integer – minimal total length of compressed strings. 样例输入
3abcatestatext
样例输出
11解题思路
上面题目的意思大概是写个程序计算压缩过后的字符串的大小，压缩的方法是把与上个字符串相同的部分直接用数字来表示，比如给出的样例，其实就是把那三个字符串压缩位
abc1test3xt代码实现min(int a, int b){if(a <= b)return a;elsereturn b;}int main(int argc, char const *argv[]){int min_len = 0;int count = 0;int num = 0;int i, j = 0;char a[255], b[255];int n ;scanf(“%d”, &n);scanf(“%s”, a);int a_len = strlen(a);count += a_len;for (j = 0; j < n – 1; j++) {scanf(“%s”,b);int b_len = strlen(b);min_len = min(a_len, b_len);count += b_len;for (i = 0; i < min_len; i++) {if(a[i] != b[i])break;}count = count – i + 1;memcpy(a, b, b_len);a_len = b_len;}printf(“%d\n”,count);return 0;}
，就是去做你害怕的事，直到你获得成功的经验。
