CF1158B The minimal unique substring 做题记录

构造一个长度为 $n$ 的 $01$ 串 $s$，使得：

• 任意长度小于 $k$ 的 $01$ 串，或者不是 $s$ 的子串，或者在 $s$ 中出现了至少 $2$ 次

• 至少存在一个长度为 $k$ 的 $01$ 串，在 $s$ 中出现了恰好一次

保证 $n\equiv k (mod 2)$。

$1\le k\le n\le 10^5$。

构造方法：设 $l=\frac{n-k}{2}$，那么 $s_i=[i\operatorname{mod} (l+1)\ge 1]$。

证明：

这样构造出来的 $s$ 一定是形如 $[1111\dots10][1111\dots10][1111\dots10][11111]$ 这样一段一段的，除了最后一段之外的每一段都是由 $l$ 个 $1$ 和 $1$ 个 $0$ 组成的。

先证明一定至少有一个长度为 $k$ 的子串只出现了一次，可以证明 $s_{[l+1,n-l]}$ 这个的长度为 $n-\frac{n-k}{2}-\frac{n-k}{2}-1+1=k$ 的子串一定是只出现一次的，因为它的开头是 $s_{l+1}=0$，而下一个最靠左的 $0$ 却在 $s_{2l+2}$，但是 $n-2l-2+1=n-n+k-2+1=k-1<k$，容不下一个长度为 $k$ 的字符串。

再来证明一定每个长度 $<k$ 的子串都出现了至少两次，设长度为 $t$，开头位置为 $p$。若 $p$ 不在第一段，显然往左移动一段即可找到相同的子串；若 $p$ 在第一段，那么往右移动一段即可。往左移动显然不会超出边界，下面来证明往右移动也不会超出边界：

显然最坏情况是 $p=l+1$，$t=k-1$，那么由于 $2l+2+k-1-1=2\frac{n-k}{2}+k=n$ 所以右端点不会超出 $n$。

综上，得证。