P8131 [ICPC 2020 WF] Gene Folding

ICPC2020 WF D

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 $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, and $\texttt{T}$ in some combination, each letter representing a single nucleotide ($\textbf{A}$denine, $\textbf{C}$ytosine, $\textbf{G}$uanine, and $\textbf{T}$hymine, 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 $\texttt{ATTACC}$, there are two such points: $\texttt{AT-TACC}$ and $\texttt{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 $\texttt{AT}$ and $\texttt{TA}$ would become merged, and the resulting sequence would be $\texttt{CCAT}$ or $\texttt{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 $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, and $\texttt{T}$ only. The length of $s$ is between $1$ and $4 \cdot 10^6$, inclusive.

Output the smallest possible length of a sequence obtained from the input by applying GOOF zero or more times.