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

点击量：175

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

目录

题目背景

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;
}