526互联

CF1200E Compress Words 字符串哈希/双重哈希

发布时间 2023-04-04 23:16:04作者: HikariFears

题目地址

题意：给你若干个字符串，答案串初始为空。第i 步将第 i 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 i 个串的前缀的字符串），求最后得到的字符串。

Solution

字符串哈希练习题，做完之后对哈希的理解更深刻了

因为求原字符串的后缀和第i个串的前缀，所以我们可以边记录第i个串的哈希值，边与原字符串进行比较

处理到第i个串的第j位时，如果j比原字符串长度大，可以直接退出

之后边给答案加入第i个串的字符，边处理答案串的哈希值

这里用了一个双hash的方法，从而减少出错率

求区间子串的哈希值

int get_hash(int l,int r,int k)
{
	return ((hs_s[r][k]-hs_s[l-1][k]*p[r-l+1][k])%m[k]+m[k])%m[k];
}

AC代码：

int b[2]={171,2333333};
int m[2]={1000000007,999999998};
int p[N][2];
int hs_s[N][2];
int hs_t[N][2];

char s[N];
string t;

void init()
{
	p[0][0]=p[0][1]=1;
	for(int i=1;i<N-3;i++)
	{
		p[i][0]=(p[i-1][0]*b[0])%m[0];
		p[i][1]=(p[i-1][1]*b[1])%m[1];
	}
}

int get_hash(int l,int r,int k)
{
	return ((hs_s[r][k]-hs_s[l-1][k]*p[r-l+1][k])%m[k]+m[k])%m[k];
}



void solve()
{
	init();
	int n;cin>>n;
	string x;
	cin>>x;
	int len=x.length();
	hs_s[0][0]=hs_s[0][1]=0;
	for(int i=1;i<=len;i++)
	{
		s[i]=x[i-1];
		for(int k=0;k<2;k++)
		{
			hs_s[i][k]=(hs_s[i-1][k]*b[k]+x[i-1])%m[k];
		}
	}
	
	for(int i=2;i<=n;i++)
	{
		cin>>t;
		hs_t[0][0]=hs_t[0][1]=0;
		int pos=1;
		int flag=1;
		for(int j=1;j<=t.length()&&len-j+1>0;j++)
		{
			flag=1;
			for(int k=0;k<2;k++)
			{
				hs_t[j][k]=(t[j-1]+hs_t[j-1][k]*b[k])%m[k];
				if(hs_t[j][k]!=get_hash(len-j+1,len,k))flag=0;
				/*cout<<hs_t[j][k]<<"\n";
				cout<<len-j+1<<" "<<len<<":"<<get_hash(len-j+1,len,k)<<"\n";*/
			}
			
			if(flag)pos=j+1;
		}
		
		for(int j=pos;j<=t.length();j++)
		{
			s[++len]=t[j-1];
			for(int k=0;k<2;k++)
			{
				hs_s[len][k]=(hs_s[len-1][k]*b[k]+s[len])%m[k];
			}
			
		}
		/*cout<<pos<<"\n";
		for(int i=1;i<=len;i++)cout<<s[i];
		cout<<"\n";*/
	}
	for(int i=1;i<=len;i++)cout<<s[i];
	cout<<"\n";
}