申必题
题意
对于一个字符串 \(S\)，求出一个字典序最小的 01 串 \(T\)，满足 \(|S|=|T|\) 且 \(S\) 和 \(T\) 的所有周期相同。
思路
首先周期可以用 KMP 跳 border 求出。于是把限制转化为 \(S\) 和 \(T\) 从结尾开始往前跳最长 border 的每个位置上的最长 border 都相同。
考虑递归构造。设 \(f(x)\) 表示长为 \(x\) 的前缀的答案。假设此时已经求出 \(f(fail(x))\)，要求 \(f(x)\)。分类讨论：
- \(2fail(x)\ge x\)，此时 \(f(x)\) 可以唯一确定。
- \(2fail(x)< x\)，此时中间剩余的部分需要被构造。
首先对于第一种情况，我们证明 \(f(x)\) 一定合法，即不存在更长的 border。如果 \(f(x)\) 存在更长的 border，那么就存在一个更小的周期，且这个周期一定也在 \(f(fail(x))\) 中存在。然后 \(f(fail(x))\) 和 \(S_{1,\cdots,fail(x)}\) 的所有周期相同，所以 \(f(x)\) 更长的这个 border 必定在 \(S_{1,\cdots,x}\) 中也是 border。这和 \(fail(x)\) 是 \(S_{1,\cdots,x}\) 的最长 border 矛盾，因此 \(f(x)\) 一定合法。
对于第二种情况，我们要找到字典序最小的构造。我们声称中间部分一定会是 \(0^{len}\) 或 \(0^{len-1}1\)。下面给出证明：
设新产生的 border 长为 \(y\)。如果 \(fail(x)+y>x\)，说明新 border 和原 border 有交，可以仿照第一种情况来证明这种串唯一。
考虑 \(fail(x)+y\le x\) 的情况。此时只有中间串全 \(0\) 且 \(f(fail(x))\) 全 \(0\) 或中间串等于 \(f(fail(x))\) 两种。\(0^{len}\) 和 \(0^{len-1}1\) 中必有一个不满足。
因此一定存在这样的构造合法。
代码
按上面过程模拟即可。
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
int n,nxt[N];
bool a[N];
bool check(int len){vector<int>f(len+1);for(int i=2;i<=len;i++){f[i]=f[i-1];while(f[i]&&a[f[i]+1]!=a[i])f[i]=f[f[i]];if(a[f[i]+1]==a[i])f[i]++;}for(int i=len;i;i=nxt[i])if(f[i]!=nxt[i])return 0;return 1;
}
void solve(){string s;cin>>s,n=s.size();for(int i=2;i<=n;i++){nxt[i]=nxt[i-1];while(nxt[i]&&s[nxt[i]]!=s[i-1])nxt[i]=nxt[nxt[i]];if(s[nxt[i]]==s[i-1])nxt[i]++;}vector<int>p;for(int i=n;i;i=nxt[i])p.push_back(i);for(int i=p.back()-1;i>=1;i--)a[i]=0;a[p.back()]=(p.back()>1);for(int i=p.size()-2;i>=0;i--){int len=p[i],flen=p[i+1];if(flen*2>len)for(int i=len;i>flen;i--)a[i]=a[flen-(len-i)];else{for(int i=1;i<=flen;i++)a[len-(flen-i)]=a[i];for(int i=flen+1;i<=len-flen;i++)a[i]=0;if(!check(len))a[len-flen]=1;assert(check(len));}}for(int i=1;i<=n;i++)cout<<a[i];cout<<'\n';
}
signed main(){clock_t _st=clock();ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();clock_t _ed=clock();cerr<<(_ed-_st)*1.0/CLOCKS_PER_SEC<<'\n';return 0;
}