농부존은 젖이 잘나오는 소들에 대한 DNA 나열을 해 보았다.
일련의 수열을 합치는 것은 가장 많이 오버랩되는 지점을 찾아서 하나로 합치는 것이다. 오버랩이란 한 문자의 끝과 다른 문자의 시작점사이가 같은 것이다. 문자열의 중간에서 오버랩되는 것은 오버랩으로 간주하지 않는다.
예를들어 , GATTACA 와 TTACA 는 완전히 오버랩된다. 반면에 GATTACA 와 TTA 는 오버랩되는 문자가 없다.
오버랩되는 , 혹은 되지 않는 몇가지 예이다.
GATTA + TACA -> GATTACA TACA + GATTA -> TACAGATTA TACA + ACA -> TACA TAC + TACA -> TACA ATAC + TACA -> ATACA TACA + ACAT -> TACAT
N ( 2 <= N <= 7 ) 이 주어질 때 각각의 문자열의 크기는 1..7 이 주어질 때 오버랩해서 만들수 있는 최소 문자열의 크기를 출력 하는 것이 문제이다.
입력 4 GATTA TAGG ATCGA CGCAT 출력 13 입력 2 TGCAG CA 출력 7
보기의 답은 13
입력이 5 TAG TGCAG CA T ACTG 답은 10
출처:USACO 2006 February Bronze