Bobo String Construction

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一字符串t，求一个长为n的字符串，使t+s+t中包含且仅包含两个t

1<=n<=1000;测试样例组数<=1000

思路：一开始很容易想到如果t里有1，s就全0，否则s就全1，但当t=a+n*0/n*1+a这样时，例如001000001,110111110,n=3，这时s就对应的不能等于全0/全1，但至少有一种可以，也就是对于前者我们可以选111，对于后者选000，所以我们全0或全1都试一下，用kmp分别检验是否合法，都不合法就输出-1（但经测试其实没有-1的情况）

#include<bits/stdc++.h>
#define P pair<int,char>
using namespace std;
const int N = 1e3 + 5;
char str[N], pattern[N];
int fail[N];
int a[N];
int n;
string t,s="";
void getfail(string p, int plen)
{//取得p的失配指针fail[0] = 0, fail[1] = 0;for (int i = 1; i < plen; i++){int j = fail[i];while (j && p[i] != p[j]){j = fail[j];}fail[i + 1] = p[i] == p[j] ? j + 1 : 0;}
}
int kmp(string s, string p)
{//求s的子串中有多少个pint cnt = 0;//记录答案int last = -1;//记录上一次匹配的位置int slen = s.size(), plen = p.size();getfail(p, plen);int j = 0;for (int i = 0; i < slen; i++){while (j && s[i] != p[j]){j = fail[j];}if (s[i] == p[j]){j++;}if (j == plen){cnt++;last = i;}}return cnt;
}
bool check()
{string temp = t + s + t;if(kmp(temp,t)>2){return false;}return true;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int T;cin>>T;while(T--){cin>>n;cin>>t;s="";for(int i=0;i<n;i++){s+="0";}if(check()){//全0试试cout<<s<<endl;continue;}s="";for(int i=0;i<n;i++){s+="1";}if(check()){//全1试试cout<<s<<endl;continue;}//cout<<"-1"<<endl;}return 0;
}