BZOJ 3555 CTSC2014 企鵝QQ

題目大意：給定n個不相同的字元串，問有多少對字元串隻差一個字母

枚舉每個隻差一個字母的位置，取除這個字元以外的哈希值判斷即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAXN 30010
#define p 137
char str[MAXN][];
int points,length;
#define ULL unsigned long long
ULL hash[MAXN][],power[MAXN],Hash[MAXN];
void Prement(){
    power[]=;
    for(int i=;i<=length;i++) power[i]=power[i-]*p;
}
inline void GetHash(char *s,ULL hash[]){
    for(int i=;i<=length;i++)
        hash[i]=hash[i-]*p+s[i];
}
inline ULL Calc_Hash(ULL hash[],int i){
    ULL ret=hash[length];
    ret=ret-hash[i]*power[length-i]+hash[i-]*power[length-i+];
    return ret;
}
int main(){
    int d;
    scanf("%d%d%d",&points,&length,&d);
    Prement();
    for(int i=;i<=points;++i){
        scanf("%s",str[i]+);
        GetHash(str[i],hash[i]);
    }
    int ans=;
    for(int i=;i<=length;++i){
        for(int j=;j<=points;j++)
            Hash[j]=Calc_Hash(hash[j],i);
        sort(Hash+,Hash+points+);
        Hash[points+]=;
        int start=;
        for(int j=;j<=points+;j++)
            if(Hash[j]!=Hash[start]){
                int cnt=j-start;
                ans+=cnt*(cnt-)>>;
                start=j;
            }

    }
    cout<<ans<<endl;
    return ;
}