洛谷 P4503 [CTSC2014]企鹅QQ 题解【字符串】【哈希】【快速乘】【枚举】

作者: wjyyy 分类: 二进制,哈希,字符串,快速乘,枚举,解题报告 发布时间: 2018-09-13 17:08

点击量:15

 

    字符串哈希的一道模板题?

 

题目背景

PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。

题目描述

小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种相似的情形进行统计。

 

小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的,但“Penguin1”和“2Penguin”不是相似的。而小Q想知道,在给定的n 个账户名称中,有多少对是相似的。

 

为了简化你的工作,小Q给你的N个字符串长度均等于L,且只包含大小写字母、数字、下划线以及‘@’共64种字符,而且不存在两个相同的账户名称。

 

输入输出格式

输入格式:

第一行包含三个正整数\(N,L,S\)。其中\(N\)表示账户名称数量,\(L\)表示账户名称长度,\(S\)用来表示字符集规模大小,它的值只可能为\(2\)或\(64\)。

 

若\(S\)等于\(2\),账户名称中只包含字符‘0’和‘1’共\(2\)种字符;

 

若\(S\)等于\(64\),账户名称中可能包含大小写字母、数字、下划线以及‘@’共\(64\)种字符。

 

随后\(N\)行,每行一个长度为\(L\)的字符串,用来描述一个账户名称。数据保证\(N\)个字符串是两两不同的。

 

输出格式:

仅一行一个正整数,表示共有多少对相似的账户名称。

 

输入输出样例

输入样例#1:

4 3 64
Fax
fax
max
mac
输出样例#1:

4

说明

4对相似的字符串分别为:Fax与fax,Fax与max,fax与max,max与mac。

测试点编号 N L S
1 50 10 64
2 500 100 64
3 3000 100 2
4 3000 100 64
5 30000 50 2
6 30000 50 64
7 30000 200 2
8 30000 200 64
9 30000 200 2
10 30000 200 64

题解:

    这个题的“相似”定义为两个字符串只有一个字符不同,同时字符串两两不同,这样就略微减小了难度。如果两个字符串只有一个位置不同,那么去掉这个位置,把它的前后给拼起来就又相同了。

 

    考虑到\(L\)的范围只有\(200\),那么可以考虑枚举哪个位置不同。先把每个字符串的hash前缀和求出来,然后每次处理各个字符串,把它们前后拼起来。这一点可以分别存它们前后的值,也可以把前后加起来,感觉前者的错误率会略低一点。

 

    于是就变成了序列中\(n\)个元素,求它们有多少对相等。这个操作是个小技巧,做法是把这些元素从小到大排序,对于一串相等的元素,假设串长为\(tmp\),则这一串元素中相等的对数有\(tmp\times (tmp-1)\)。这里的复杂度是\(O(n\log n)\)。

 

    加上上面枚举每一位的复杂度,把哈希的指数快速幂预处理出来,就可以让整个程序的复杂度变为\(O(nL\log n)\)。

 

    对于字符集大小,只是改变了哈希所乘的数的底数,甚至无论读入是\(2\)还是\(64\),所有字符集大小都认为是\(64\)也可以。不过有一点需要注意,根据生日悖论,这里的模数要尽可能大,因为在\(O(\sqrt{64^{200}})=O(64^100)\)的范围内就会有很大的几率冲突(主要还是看脸)。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
const long long mod=1000000000039ll;
char c[30010][205];
long long num[128];
void init()//初始化字符集的映射
{
    for(int i='0';i<='9';++i)
        num[i]=i-47;
    for(int i='@';i<='Z';++i)
        num[i]=i-53;
    num['_']=38;
    for(int i='a';i<='z';++i)
        num[i]=i-58;
}
long long qmul(long long x,long long y)//模数大了用快速乘
{
    long long ans=0,m=x;
    while(y)
    {
        if(y&1)
            ans=(ans+m)%mod;
        m=2*m%mod;
        y>>=1;
    }
    return ans;
}
long long qpow(long long x,long long y)
{
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans=qmul(ans,m);
        m=qmul(m,m);
        y>>=1;
    }
    return ans;
}
long long sum[30010][203];
struct Hash//前后分别存,复杂度也不是太高
{
    long long pre,suc;
    friend bool operator <(Hash A,Hash B)
    {
        if(A.pre!=B.pre)
            return A.pre<B.pre;
        return A.suc<B.suc;
    }
    friend bool operator ==(Hash A,Hash B)
    {
        return A.pre==B.pre&&A.suc==B.suc;
    }
}b[30100];
long long Pow[205];
int main()
{
    init();
    int n,m,bs;
    scanf("%d%d%d",&n,&m,&bs);
    for(int i=0;i<=200;++i)
        Pow[i]=qpow(bs+1,i);
    for(int i=1;i<=n;++i)
        scanf("%s",c[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            sum[i][j]=(sum[i][j-1]+num[c[i][j]]*Pow[j-1])%mod;//前面的次数低
    long long ans=0;
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            b[j].pre=sum[j][i-1];
            b[j].suc=(sum[j][m]-sum[j][i]+mod)%mod;
        }
        sort(b+1,b+1+n);//排序并统计
        long long tmp=0;
        for(int j=1;j<=n;++j)
            if(b[j]==b[j-1])
                ++tmp;
            else
            {
                ans+=tmp*(tmp+1)/2;
                tmp=0;
            }
        ans+=tmp*(tmp+1)/2;
    }
    printf("%lld\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */