Description

官方 PDF 题面

Idea

我们需要一种能一次确定一位的高效询问算法。

考虑到 $p$ 的最大长度为 $4n$,$S$ 的首字母只出现一次,那么我们每次可以基于已知的前缀 $s$,询问 $4$ 种可能的情况。

不妨设 $S$ 的首字母为 $A$,对于已知的前缀 $s$,我们询问

$$sXBsXXsXYsB$$

如果返回值比当前长度大 $2$,说明下一位是 $X$;大 $1$,说明下一位是 $B$,否则下一位为 $Y$。

对开头和结尾的两个字符做二分查找,总询问次数为 $n+2$。

Code