解题思路

“幸运字符串”指长度为偶数且前半部分与后半部分完全相同（空串也算）。 把 ? 看作可变的通配符：当成对字符都已知且不同，才 必定冲突；若有 ? 或相同，则能被补成相同。

错误回顾：我之前用了“对半长度 k 的可行性关于 k 单调”的假设做二分，但该假设是假的。样例 jum??ump 中，k=3 不可行而 k=4 可行，即并不单调，因此二分会错。

正确做法（线性滑窗 + 枚举间距）：

题目内容

幸运字符串:如果它的长度是偶数并且前一半与后一半完全一致，例如 $"abcabc”,"aaaa"$，特别地，空字符串 " " 也被认为是幸运字符串。

一个字符串的幸运值被定义为它的所有子串中，最长的幸运字符子串的长度。

例如在字符串 $"abbc"$ 中，它的子串为 $["abbc","abb","bbc","ab","bb","bc","a","b","c",”]$，而其中幸运字符子串为 $["bb",$" "$]$，所以 $"abbc"$ 的幸运值为 $"bb"$ 的长度,即 $"abbc”$ 的幸运值为 $2$ 。

多多发现了一张古老的魔法卷轴，上面写有一个由 $a-z$ 组成的字符串，其中某些字符因为时间久远已经无法辨认，无法辨认的字符使用 “$?$" 表示。魔法卷轴的等级由它上面记载的字符串的幸运值决定，多多希望为每个无法辨认的字符 "$?$" 填入一个字母 $(a-z)$ ,使得整个字符串的幸运值最大。

例如在字符串 $"aa?ab"$ 中，可以将 $"?"$ 替换成 $"a"$，这样填充形成新字符串 $"aaaab"$ ，其最长幸运字符子串为 $"aaaa"$ ，幸运值为 $4$ 。

请为多多计算一下填充后的字符串最大可能的幸运值是多少?

输入描述

共一行，包括多多在魔法卷轴上发现的字符串 $s$ ，其中每个字符均为 $a-z$ 或者 $?$ 之一，$?$ 表示无法辨认的字符。字符串长度 $|s|$ 满足 $1 ≤|s|≤ 5000$

输出描述

共 $1$ 行，包含一个整数，表示填充后的字符串最大可能的幸运值

样例1

输入

aaaaa

输出

4

说明

子串中最长的幸运字符串为 $aaaa$ ，长度为 $4$

样例2

输入

jum??ump

输出

8

说明

可以将字符串填充为 $jumpjump$ ，其本身就为幸运字符串，长度为 $8$

样例3

输入

dj?aaaaam

输出

6

说明

可以将字符串填充为 $djaaaaaam$ ，子串中最长的幸运字符串为 $aaaaaa$ ，长度为 $6$