第十一届山东省大学生程序设计竞赛(Birthday Cake)

第十一届山东省大学生程序设计竞赛(Birthday Cake)

做法双哈希
由题意可知：有几对字符串可以组成前后一样的字符串，类似于abcabc此类；
解法：if(字符串前后缀相同) 就检查去掉前后缀之后的字符串出现过几次ans+=这个次数；
举个栗子： cabc 这个字符串前后缀 c 相同 就看ab出现过几次 ab和cabc就可以组成abcabc；

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define ull unsigned long long 
#define pll pair<ull,ull>
const int maxn=4e5+5;
ull hs1[maxn],hs2[maxn],pec=131,peac1[maxn],peac2[maxn];
ull mod1=1e9+7,mod2=1e9+11;
pll res[maxn];
map<pll, ull> cnt;
ull get1(int l,int r){
    return (hs1[r]-hs1[l-1]*peac1[r-l+1]%mod1+mod1)%mod1;//一定要去两次mod
}
ull get2(int l,int r){
    return (hs2[r]-hs2[l-1]*peac2[r-l+1]%mod2+mod2)%mod2;    
} 
pll get(int l,int r){
    return {get1(l,r),get2(l,r)};
}
int id=0;
int main(){
    peac1[0]=1;
    peac2[0]=1;//初始化进制
    for(int i=1;i<maxn;i++) peac1[i]=peac1[i-1]*pec%mod1;
    for(int i=1;i<maxn;i++) peac2[i]=peac2[i-1]*pec%mod2;
    int n;
    cin>>n;
    while(n--){
        char s[maxn];
        cin>>s+1;
        int len=strlen(s+1);
        for(int i=1;i<=len;i++){
            hs1[i]=(hs1[i-1]*pec%mod1+(s[i]-'a'+1))%mod1;
            hs2[i]=(hs2[i-1]*pec%mod2+(s[i]-'a'+1))%mod2;
        }    
        cnt[{hs1[len],hs2[len]}]++;//记录出现的字符串双哈希
        for(int i=1;i+i<len;i++){
            if(get(1,i)==get(len-i+1,len)){ //前后缀双哈希值相等
                res[++id]=get(i+1,len-i); //存入res数组
            } 
        }
    }
    ull ans=0;
    for(int i=1;i<=id;i++) {  //ans+=出现次数即为所得
        ans+=cnt[res[i]];
    }
    for(auto it : cnt) ans += it.second * (it.second - 1) / 2;
    //如果是相同的字符串就可以组成（（n-1）*n）/2个答案
    cout<<ans<<'\n';
}

当我们遇见哈希题时 如果单哈希解决不了 可以试试双哈希来解决 现在大多数出题人喜欢卡单哈希T_T~
祝大家天天AC