依靠子串猜原文

l4m2

猜測一個長度為$n$的01串$S$。對任意串$s$，可隨時以$|s|$的代價判斷$s$是否$S$的子串。
問能否以$\text{O}\left(n\log^k n\right)$的代價，多項式的算力，求出$S$？

顯然，$\text{O}\left(n)$是不可能的，因為至少需要$\text{O}\left(n\log n\right)$的代價來問$n$個不同的問題。