P4503 企鹅QQ 题解

lcy09 · 2020-07-11 16:38:05 · 个人记录

题面

P4503 企鹅QQ

分析

因为是字符串比较，还是看只有一位的差异，所以用哈希来求解。具体思想就是枚举每一位，算出每一个串去掉枚举的这位之后的hash值，然后排序，易求得相似的字符串对数。

代码

#define ULL unsigned long long
const int MAXN=30005;
const int MAXL=205;
const int base=163;
const int mod=1e9+7;
int n,l,s;
ULL bit[MAXL];//预处理base^i的数组
ULL mes[MAXN][MAXL],has[MAXN];//mes是从高位向低位依次进行的hash值，has是枚举去位的数组
void init()//预处理
{
    bit[0]=1;
    for(int i=1;i<=l;i++) bit[i]=bit[i-1]*base;
}
string a[MAXN];//原字符
int ans;
int main()
{
    cin>>n>>l>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=l;j++) mes[i][j]=mes[i][j-1]*base+a[i][j-1];//从高向低一位位算出hash，方便后面的处理
    }
    for(int i=1;i<=l;i++)//枚举第i位
    {
        for(int j=1;j<=n;j++)
        {
            has[j]=mes[j][i-1]*bit[l-i]+mes[j][l]-mes[j][i]*bit[l-i];//hash总值+前(i-1)位移位后的hash-前i位移位后的hash=去掉第i位的hash
        }
        sort(has+1,has+n+1);
        int cnt=1;//以下几行是巧妙地弄出相似的字符串对的数量
        for(int j=1;j<=n;j++)
        {
            if(has[j]!=has[j-1]) cnt=1;
            else 
            {
                ans+=cnt;
                cnt++;
            }
        }
    }
    cout<<ans<<endl;
return 0;
}