A.Bobo String Construction

构造

题目大意

给定一个标识01串 $tt$ ，构造一个长度为 $nn$ 的信息01串 $ss$ ，使得串 $m=t+s+tm=t+s+t$ 中，串$tt$ 仅在开头和结尾各出现过一次。（其中 $++$ 表示字符串连接运算）

解题思路

考虑构造 $ss$ 全为 $00$ 或 $11$

对于特殊情况， $tt$ 全为 $00$ 或 $11$ ，则使 $ss$ 全为 $11$ 或 $00$ 即可

如果 $tt$ 中兼有 $00$ 和 $11$ ，则 显然 $ss$ 中不可能有子串 $tt$

但对于 $m=t+s+tm=t+s+t$ ，可能有 $t\mathrm{的}\mathrm{后}\mathrm{缀}+s+t\mathrm{的}\mathrm{前}\mathrm{缀}=tt的后缀+s+t的前缀=t$ 的情况出现，导致不满足题设条件//

那么下面感性证明一下两种方案至少有一种成立。

假设对于兼有 $00$ 和 $11$ 的 $tt$ ，在 $ss$ 全为 $00$ 的情况下出现：

$t\mathrm{的}\mathrm{后}\mathrm{缀}+s+t\mathrm{的}\mathrm{前}\mathrm{缀}=tt的后缀+s+t的前缀=t$

那么构造 $ss$ 全为 $11$ 即可，反之亦然

于是问题就转化为在 $ss$ 全为 $11$ 或 $00$ 的方案中选择一种使得串$tt$ 仅在开头和结尾各出现过一次

先使 $ss$ 全为 $11$ 将 $m=t+s+tm=t+s+t$ 去掉首尾一个字符，判断中间有无字串 $tt$ 即可

归纳发现特殊情况也可以用这种方法构造

时间复杂度

数据范围小（ $n\le 1000,\mathrm{\mid }t\mathrm{\mid }\le 1000n\backslash le\; 1000,|t|\backslash le\; 1000$ ），BF即可

参考程序

void solve()
{
    string t;ll n;
    cin >> n >> t;
    string s;FORLL(i,1,n) s.push_back('1');
    string m=t+s+t;m.erase(m.begin());m.pop_back();
    if(m.find(t)!=string::npos) FORLL(i,1,n) cout << '0';
    else FORLL(i,1,n) cout << '1';
    cout << endl;
}