1754: [搜索][回溯][递归]奶牛的DNA

 Farmer John最近弄到了奶牛贝茜的DNA序列。象我们熟知的那样，贝茜的DNA
序列是一个由字母'A','C','G','T'组成的字符串。

    在普通的DNA测试中，我们一般得到的只是DNA的片段，而不是整个序列。比如
说，形如'GATTA'和'TACA'的两个片段，很可能是对总序列'GATTACA'进行两次测试
后得到的。在对DNA序列的多次测试后，得到的片段两两之间可能有一定的重复。

    合并两个片段，需要找到这两个片段的最长重复子串，删掉其中的一个后把两
个片段首尾相连。如果某个串完整地出现在某个片段的尾部与另一个片段的开始部
分，我们就称它为这两个片段的重复子串。注意，出现在某个片段中间的串不可能
成为重复子串。

    比如说，片段'GATTACA'和'TTACA'的重复子串就是'TTACA'，而序列'GATTACA'
和'TTA'就没有重复子串，因为'TTA'出现在'GATTACA'的中间，不是开头或者末尾。
以下是一些片段合并的例子，其中包括没有重复子串的情况。

    GATTA + TACA -> GATTACA
    TACA + GATTA -> TACAGATTA
    TACA + ACA -> TACA
    TAC + TACA -> TACA
    ATAC + TACA -> ATACA
    TACA + ACAT -> TACAT

    我们的任务是：对于给出的N(2<=N<=7)个长度不超过7个字符的DNA片段，求出
它们首尾相连所形成的总序列的最短长度。所有的片段都必须被接入总序列。

程序名: dna
 

输入格式:

* 第1行: 只有一个整数N，表示DNA片段的总数

* 第2..N+1行: 每行是一个DNA片段的具体描述

输出格式:

* 第1行: 输出只有一个整数，表示所有片段按某种顺序首尾接在一起所得DNA总
         序列的最小长度。

4
GATTA
TAGG
ATCGA
CGCAT

13