https://codeforces.com/contest/1138/problem/D

题意

两个01串s和t,s中字符能相互交换,问最多能得到多少个(可交叉)的t

题解

• 即将s中的01塞进t中,预处理出next(tlen),然后每次填完移到next(tlen)继续填即可

代码

#include<bits/stdc++.h>

using namespace std;

int sl,pl,i,j,a,b,e,f,nt[500005];

string s,p;

void get_nt(){

	int plen=p.size(),j=0,k=-1;

	nt[0]=-1;

	while(j<plen){

		if(k==-1||p[k]==p[j]){

			k++;j++;

			nt[j]=k;

		}else k=nt[k];

	}

}

int main(){

	cin>>s>>p;

	sl=s.size();pl=p.size();

	get_nt();

	for(i=0;i<pl;i++){

		if(p[i]=='0')a++;

		else b++;

	}

	for(i=0;i<sl;i++){

		if(s[i]=='0')e++;

		else f++;

	}

	if(e>=a&&f>=b){

		e-=a;f-=b;

		for(i=0;i<pl;i++)s[i]=p[i];

		j=nt[pl];

	}else{

		cout<<s<<endl;

		return 0;

	}

	while(1){

		if(!e||!f){

			if(e){

				for(j=0;j<e;j++)s[i++]='0';

				break;

			}else{

				for(j=0;j<f;j++)s[i++]='1';

				break;

			}

		}

		if(p[j]=='0'){

			s[i++]='0';

			j++;

			e--;

		}else{

			s[i++]='1';

			j++;

			f--;

		}

		if(j==pl)j=nt[j];

	}

	cout<<s<<endl;

}