Given a string  of length , let’s define the neighbors of the -th character () as follows:

  • If , the neighbors of the -th character are the -th character and the -th character;
  • If , the neighbors of the 1st character are the 2nd character and the -th character;
  • If , the neighbors of the -th character are the -th character and the 1st character.

A string  is good, if and only if all the characters in the string are different from their neighbors.

DreamGrid would like to delete  continuous characters from string  to form a new string . Note that the -th character and the 1st character are also continuous (you can consider the string as a ring). Please tell him if it’s possible to make  a good string for all .

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first and only line contains a string  () consists of lowercase English letters.

It’s guaranteed that the sum of  over all test cases will not exceed .

Output

For each test case output one line containing one string of length  consists of ‘0’ and ‘1’. If the -th (the index starts from 1) character is ‘1’, it is possible to make  a good string; If its ‘0’, it is impossible to make  a good string.

Sample Input

5
abab
aabbaa
abcabc
abcdef
a

Sample Output

1011
000011
110111
111111
1

【题解】题目大意是说给你一个环装字符串,让你给出删除x个(1<=x<=len)连续的字符,剩下的字符能不能满足相邻两个不相等。

这个数据范围肯定要O(n)的算法了。

我们考虑剩下的串,可以线性地找出相邻不相等的所有长串,找到每一个长串之后开始考虑删除长度为i的连续的串能不能满足要求。

因为串内满足性质..所以只要枚举首位就行了。

假设长串是s[i]~s[j]

那么只要(s[i],s[i+len-1])(s[i+1],s[i+1+len-1])…中有一组不一样就可以了。

我们可以蛤希判断。

/********************************************

	Title		ZOJ4010.cpp
	Author 		TomatoLoveCoconut
	Time		2018-4-01
	History		Created 2018-4-01
	
	Version		1.0.0
	
	Tags:
			Hash

	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define eps 1e-9
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 2000010


using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var
ll Hash[maxn];
ll pos[maxn];
inline ll getHash(int l,int r)
{
	return ((Hash[r]-(ll)Hash[l-1]*pos[r-l+1])%mod+mod)%mod;	
}
char s[maxn];
int ans[maxn];

int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	pos[0]=1;
	for (int i=1;i<=2000000;i++)
		pos[i]=(ll)(pos[i-1]*base)%mod;
	int T;
	scanf("%d",&T);
	while (T--)
	{
		cla(Hash);
		cin>>s+1;
		int n=strlen(s+1);
		for (int i=1;i<n;i++)
		{	
			s[n+i]=s[i];
		}
		for (int i=1;i<=n*2-1;i++)
			Hash[i]=((ll)Hash[i-1]*base+s[i])%mod;
		cla(ans);
		for (int i=1,j;i<n*2-1;i=j+1)
		{
			j=i;
			for (;j<n*2-1 && s[j]!=s[j+1];j++);
			int len=j-i+1;
			for (int k=2;k<=len && k<=n;k++)
			{
				if (getHash(i,j-k+1)!=getHash(i+k-1,j))
					ans[n-k]=1;
			}
		}
		for (int i=0;i<=n-2;i++)
			printf("%d",ans[i]);
		puts("1");
	}
	return 0;
}













/******************************************************
		Any Questions Please Contact Me
		Tencent QQ:	898021802
		Website:	primopan.org
		Email:		primojpan@gmail.com
*******************************************************/
分类: Hash

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注