首页 > 其他 > 详细

luogu_4503【题解】企鹅QQ 哈希

时间:2019-07-06 21:34:36      阅读:116      评论:0      收藏:0      [点我收藏+]

题面:https://www.luogu.org/problemnew/show/P4503

可以用哈希来做。

因为题目说两两不重复所以更简单了。

正着一遍反着一遍。

枚举中间点求两边。

若相等则是相似。

不重复所以不用管中间这位。

代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,l,s;
const int maxn=3e4+2;
char c[300];
unsigned long long h1[maxn][300],h2[maxn][300],t[maxn];
inline void hs(int x){
    for(int i=1;i<=l;i++) h1[x][i]=h1[x][i-1]*149+c[i];
    for(int i=l;i>=1;i--) h2[x][i]=h2[x][i+1]*137+c[i];
}
int main()
{
    scanf("%d%d%d",&n,&l,&s);
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        hs(i);
    }
    int ans=0;
    for(int i=1;i<=l;i++){
        for(int j=1;j<=n;j++) 
            t[j]=h1[j][i-1]*233+h2[j][i+1]*213;
        sort(t+1,t+1+n);
        int now=1;
        for(int j=2;j<=n;j++){
            if(t[j]==t[j-1]) ans+=now,now++;
            else now=1;
        }
    }
    cout<<ans<<endl;
    // system("pause");
    return 0;
}

 

luogu_4503【题解】企鹅QQ 哈希

原文:https://www.cnblogs.com/ChrisKKK/p/11144089.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!