#P18521. Game of Strings
Game of Strings
Game of Strings
小 P 和小 B 喜欢玩游戏,于是找到小 Skip。Skip 向他们介绍了下面这个游戏。
初始有一个由小写英文字母组成的字符串 ,其初值是 Skip 给定的 。小 P 和小 B 的初始得分均为0。两人轮流操作,小 P 先手。当前操作的一方选择 的一个非空前缀(允许选择整个 ),获得等于这个前缀在当前字符串 中出现次数的分数,然后从 开头删除这个前缀。
出现位置可以相互重叠,所选前缀在开头的那次出现也计入分数;这里计算的是删除前的当前字符串中的出现次数。某次操作后 变为空串,游戏立即结束。
例如,可以进行如下游戏过程:
- 初始 。
- 小 P 选择前缀 ,获得3分, 变成 。
- 小 B 选择前缀 ,获得2分, 变成 。
- 小 P 选择 ,获得1分,字符串变空,游戏结束。最后小 P 得4分、小 B 得2分。
小 P 希望最大化“小 P 的得分减去小 B 的得分”,小 B 希望最小化这个值。假设双方都绝顶聪明,求游戏结束时该差值。
输入格式
一行一个只含小写英文字母的字符串 ,保证 。只有一组输入。
输出格式
输出一行一个整数,表示双方均采取最优策略时,小 P 的得分减去小 B 的得分。
原样例 1
输入:
ababa
输出:
2
原样例 2
输入:
letitrotwillwinworldfinals
输出:
4