{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003eFarmer John对获奖的奶牛进行了DNA测序,奶牛们的DNA序列是一个字符串,字符串中包含字母 \u0027A\u0027, \u0027C\u0027, \u0027G\u0027,\u0026nbsp;\n\u003cbr\u003e 和 \u0027T\u0027。通常DNA测序的结果是一组字符串,即一系列的DNA片段,而不是整个DNA字符串。例如两个字符串\u0027GATTA\u0027\u0026nbsp;\n\u003cbr\u003e 和 \u0027TACA\u0027,最有可能代表的字符串是\u0027GATTACA\u0027。重叠的字符有可能是被多次测序,所以将他们合并。合并两个字\n\u003cbr\u003e 符串需要找到它们两个最多的重叠部分,当两个字符串连接在一起的时候消除重叠部分。重叠部分指的是在一个字\n\u003cbr\u003e 符串的开头同时又在另一个字符串的结尾,而在一个字符串的中间不算。举例,字符串\u0027GATTACA\u0027 和 \u0027TTACA\u0027完全\n\u003cbr\u003e 重叠。而字符串\u0027GATTACA\u0027 和 \u0027TTA\u0027没有任何重叠,因为匹配的字符出现在另一个的中间,既不在头也不在尾。这\n\u003cbr\u003e 里有一些合并字符串的例子,包括没有重叠部分的:\n\u003cbr\u003e GATTA + TACA -\u0026gt; GATTACA\u0026nbsp;\n\u003cbr\u003e TACA + GATTA -\u0026gt; TACAGATTA\u0026nbsp;\n\u003cbr\u003e TACA + ACA -\u0026gt; TACA\u0026nbsp;\n\u003cbr\u003e TAC + TACA -\u0026gt; TACA\u0026nbsp;\n\u003cbr\u003e ATAC + TACA -\u0026gt; ATACA\u0026nbsp;\n\u003cbr\u003e TACA + ACAT -\u0026gt; TACAT\u0026nbsp;\n\u003cbr\u003e 给出一组N(2 \u0026lt; \u003d N \u0026lt; \u003d 7)个DNA片段(字符串),长度都在1..7之间。\u0026nbsp;\n\u003cbr\u003e 找出使用上述规则合并所有字符串(可打乱顺序),能够得到的最短序列长度。所有的字符串都必须合并到结果序\n\u003cbr\u003e 列中去。\u0026nbsp;\n\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan\u003e行1:一个整数N\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e \n\u003cspan\u003e行2..N+1:每行包含一个DNA片段\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cspan\u003e行1:可以得到的最短序列的长度。它是将输入的所有字符串(可打乱顺序)进行合并能够达到的最小长度。\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e4 \r\nGATTA \r\nTAGG \r\nATCGA \r\nCGCAT \u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eSample Output\u003c/h2\u003e\n\u003cpre class\u003dcontent\u003e\u003cspan class\u003dsampledata\u003e13 \r\nHint \r\nExplanation of the sample: \r\nSuch string is \"CGCATCGATTAGG\". \u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e13 \r\nHint \r\nExplanation of the sample: \r\nSuch string is \"CGCATCGATTAGG\". \u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}