第二周 递归：1.SIMPLE PREFIX COMPRESSION

总时间限制:

2000ms

内存限制:

65536kB

描述

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A1, ..., ANby the following method: if there are strings Ai = ai,1ai,2...ai,pand 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.

样例输入

3
abc
atest
atext

样例输出

11

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[10005][300];
int main(int argc,const char *argv[])
{
    int n = 0;
    int tep = 0;
    scanf("%d", &n);
    for(int i = 0; i < n ; i++)
    {
        scanf("%s", s[i]);
    }
    int sum =(int)strlen(s[0]);
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < strlen(s[i]) && j < strlen(s[i - 1]); j++)
        {
            if(s[i][j] == s[i - 1][j]) tep++;
            else {sum =sum + (int)strlen(s[i]) - tep + 1; tep = 0; break;}
        }
        if(tep) {sum =sum + (int)strlen(s[i]) - tep + 1; tep = 0;}
    }
    printf("%d\n", sum);
}