l4m2 发表于 2023-5-14 19:47:59

依靠子串猜原文

猜測一個長度為$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$個不同的問題。
页: [1]
查看完整版本: 依靠子串猜原文