#P18521. Game of Strings

Game of Strings

Game of Strings

小 P 和小 B 喜欢玩游戏,于是找到小 Skip。Skip 向他们介绍了下面这个游戏。

初始有一个由小写英文字母组成的字符串 SS,其初值是 Skip 给定的 S0S_0。小 P 和小 B 的初始得分均为0。两人轮流操作,小 P 先手。当前操作的一方选择 SS 的一个非空前缀(允许选择整个 SS),获得等于这个前缀在当前字符串 SS 中出现次数的分数,然后从 SS 开头删除这个前缀。

出现位置可以相互重叠,所选前缀在开头的那次出现也计入分数;这里计算的是删除前的当前字符串中的出现次数。某次操作后 SS 变为空串,游戏立即结束。

例如,可以进行如下游戏过程:

  • 初始 S0=ababaS_0=\texttt{ababa}。
  • 小 P 选择前缀 a\texttt a,获得3分,SS 变成 baba\texttt{baba}。
  • 小 B 选择前缀 ba\texttt{ba},获得2分,SS 变成 ba\texttt{ba}。
  • 小 P 选择 ba\texttt{ba},获得1分,字符串变空,游戏结束。最后小 P 得4分、小 B 得2分。

小 P 希望最大化“小 P 的得分减去小 B 的得分”,小 B 希望最小化这个值。假设双方都绝顶聪明,求游戏结束时该差值。

输入格式

一行一个只含小写英文字母的字符串 S0S_0,保证 1≤∣S0∣≤1061\le|S_0|\le10^6。只有一组输入。

输出格式

输出一行一个整数,表示双方均采取最优策略时,小 P 的得分减去小 B 的得分。

原样例 1

输入:

ababa

输出:

2

原样例 2

输入:

letitrotwillwinworldfinals

输出:

4