[CTSC2014]企鹅QQ

Posted on | In

这道题是一道哈希的裸题

其实学长之前上课讲哈希的时候顺带讲过

只是当时我在干嘛？？？

先把所有字符串的哈希值都预处理出来

然后枚举哪一位不一样

把所有字符串这一位前缀和后缀的哈希值加起来

最后判断刚才计算的哈希值是否相等并且统计答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int l,m,n,ans,now;
char s[202];
unsigned long long t[30003];
unsigned long long _hash[30003][202];
unsigned long long hash_[30003][202];
int main()
{
    scanf("%d%d%d",&n,&l,&m);
    for(register int i=1;i<=n;++i)
    {
        scanf("%s",s+1);
        for(register int j=1;j<=l;++j) _hash[i][j]=_hash[i][j-1]*223+s[j];
        for(register int j=l;j>=1;--j) hash_[i][j]=hash_[i][j+1]*233+s[j];
    }
    for(register int i=1;i<=l;++i)
    {
        for(register int j=1;j<=n;++j) t[j]=_hash[j][i-1]*229+hash_[j][i+1]*239;
        sort(t+1,t+n+1);now=1;
        for(register int j=2;j<=n;++j) t[j-1]==t[j]?ans+=now++:now=1;
    }
    printf("%d\n",ans);
    return 0;
}