P6724 题解

damnM3bro · 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;
}