[题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Hash

题目描述

给定字符串T，要求求字符串S，满足以下条件：

• S是T的前缀
• S和T运行某段代码的哈希值相同（代码见下）
• T只包含小写字母
• S和T的长度差不超过50

哈希代码：

//Language C++14
long long mod=5999993;
long long gethas(string s)
{
    long long ret=0;
    for (char c:s)
    ret=(ret*29+(c-'a'+1))%mod;
    return ret;
}

题解
先分析这段哈希代码。取的模数mod=5999993，位权值为29（相当于29进制）。
那么可以得到29^6约为mod*100，远大于mod。
设S的哈希值为X，将X左移六位的哈希值为Y。可以枚举一个i，使i倍mod+X=H+Y。
其中H是可以用六位小写字母表示的哈希值。
由于a-z可以表示1-26的所有数，对于29进制，只要每一位的数满足>0且<26即可用小写字母表示。
每次查询能够找到的概率为（26/29)^6 ,约等于0.51。玄学复杂度，但可以跑过。

代码

#include<bits/stdc++.h>
#define  int  long long
using namespace std;
const int mod=5999993;
int q_pow(int a,int x){
	int ans=1,base=a;
	while(x){
		if(x&1)(ans*=base)%=mod;
		(base*=base)%=mod;
		x>>=1;
	}
	return ans;
}
bool check(int x){
	int ans[10];
	int p=0;
	while(x){
		ans[++p]=x%29;
		x/=29;
		if(ans[p]<=0||ans[p]>26)return false;
	}
	if(p!=6)return false;
	for(int i=p;i>=1;i--)cout<<(char)('a'+ans[i]-1);
	cout<<"\n";
	return true;
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		cout<<s;
		int x=0,f=1;
		for(int i=s.length()-1;i>=0;i--)(x+=((int)(s[i]-'a'+1)*f))%=mod,(f*=29)%=mod;
		int y=x;
		int flag=0;
		while(1){
			(y=q_pow(29,6)*y)%=mod;
			for(int i=0;i<=100;i++){
				int delta=x+mod*i-y;
				if(check(delta)){
					flag=1;
					break;
				}
			}
			if(flag)break;
		} 
	}
}