自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:23:23，当前版本为作者最后更新于2024-03-09 15:05:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意分析

给定字符串，求最小词根。

解题方法

枚举词根的长度，切片并判断哈希值即可。

AC 代码

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int hash_str(string k){
	int ans=0;
	for(int i=0;i<k.size();++i)
		ans+=k[i]*k[i];
		//普通的进制哈希无法判断两个字符串字母改变顺序后能否完全相同
		//如 "ab" 与 "ba" 的哈希值是不相等的 
		//故计算字符串每一位的 Ascii 码值的平方之和 
	return ans;
}
signed main(){
	string k;
	cin>>k;
	int sizeof_k=k.size();
	for(int i=1;i<=k.size()-1;++i){		//枚举词根长度 
		if(sizeof_k%i==0){	 
			int xb=i;
			bool kk=true;
			int right=hash_str(k.substr(0,i));    //词根哈希值 
			while(xb<sizeof_k){
				if(hash_str(k.substr(xb,i))!=right){
					kk=false;
					break;
				}
				xb+=i;
			}
			if(kk==true){     
				cout<<k.substr(0,i);
				return 0;
			}
		}
	}
	cout<<-1;
}