P10215 [CTS2024] String Game

Xiao P and Xiao B like playing games. They found skip. skip told them about the following game: - There is a string $S$ consisting of lowercase letters. When the game starts, it is the string $S_0$ given by skip. The game scores points for Xiao P and Xiao B, and initially both of their scores are $0$. - Xiao P and Xiao B take turns operating on this string, with Xiao P moving first. On each turn, the current player can do the following: - Choose a non-empty prefix of $S$ (it may be $S$ itself), gain points equal to the number of occurrences of this prefix in $S$, and then delete this prefix from $S$. - If after some operation $S$ becomes empty, the game ends. To help you better understand the rules, consider the following example: - Initially, $S_0 = ababa$. - Xiao P chooses the prefix $a$ of $ababa$, gains 3 points, and $S$ becomes $baba$. - Xiao B chooses the prefix $ba$ of $baba$, gains 2 points, and $S$ becomes $ba$. - Xiao P chooses $ba$, gains 1 point, the string becomes empty, and the game ends. Finally, Xiao P gets 4 points and Xiao B gets 2 points. Xiao P wants to maximize (Xiao P's score minus Xiao B's score), while Xiao B wants to minimize this value. They want to know, assuming both players are perfectly smart, what the final value of (Xiao P's score minus Xiao B's score) will be.

Read from standard input. The input contains only one line: a string $S_0$ consisting of lowercase letters.

Write to standard output. Output one integer, representing the value of (Xiao P's score minus Xiao B's score) when the game ends, assuming both players are perfectly smart.

**Sample 1 Explanation** The optimal strategies of Xiao P and Xiao B are the strategy given in the problem description. ### Subtasks Let $n$ be the length of the string $S$. For all testdata, $1 \le n \le 10^6$, and the string $S$ consists of lowercase letters. | Subtask ID | $n \le$ | Special Property | Points | |-----------|------------------|-------------------------------------------------------|--------| | 1 | $5 \times 10^3$ | None | 10 | | 2 | $10^6$ | Each character of $S$ is independently uniform in $\{a,b\}$ | 10 | | 3 | $10^6$ | Every character of $S$ is $a$ | 5 | | 4 | $2 \times 10^5$ | Every character of $S$ is $a$ or $b$ | 25 | | 5 | $5 \times 10^5$ | None | 25 | | 6 | $10^6$ | None | 25 | Translated by ChatGPT 5