International Cell Processing Company (ICPC) is a world leader in the analysis of genetic sequences. A genetic sequence is a sequence of nucleotides, which in this problem is represented by a string containing only the letters A, C, G, and T in some combination, each letter representing a single nucleotide (Adenine, Cytosine, Guanine, and Thymine, respectively).
One of the key discoveries made by ICPC is that through a process called Genetically Optimized Organic Folding (GOOF), they can take a genetic sequence and transform it into a simpler one, while preserving many of the properties of the sequence that ICPC wants to analyze.
A single application of GOOF works as follows. Find a point between two adjacent nucleotides in the nucleotide sequence, such that the sequence reads the same from that point in both directions, up until the nearer end of the sequence. For instance, in the sequence ATTACC, there are two such points: AT-TACC and ATTAC-C. Then pick one of these points (say, the first one), and fold the genetic sequence at that point, merging the identical nucleotides (so, in this case the AT and TA would become merged, and the resulting sequence would be CCAT or TACC).
Through repeated application of GOOF, a nucleotide can potentially be made much shorter. However, manually searching for the appropriate folding points is very time-consuming. ICPC reached out to you to write a program that would automate the process of finding the folding points and choosing them so as to obtain the shortest possible genetic sequence from a given input sequence.
The input contains a single string s representing the nucleotide sequence to be analyzed. The string consists of characters A, C, G, and T only. The length of s is between 1 and 4．106, inclusive.
Output the smallest possible length of a sequence obtained from the input by applying GOOF zero or more times.
ATTACC
3
AAAAGAATTAA
5
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||