解题报告 P4503 【[CTSC2014]企鹅QQ】

清风我已逝 · 2018-08-02 15:15:00 · 题解

夏令营讲了，回来巩固一下

1.预处理，算出前i段的哈希值（这里使用的为进制哈希）
2.根据题意，枚举不同位是哪一位，
  求所有字符串在去掉这一位后的哈希值，
  用排序等方法统计相同的对数。
3.O(lnlog2n)

那么如何求去掉一位的哈希值呢？

设去掉第k位,长度为l

HS=hs[i-1]*base^(l-i)+hs[l]-hs[i]*base^(l-i);

#include<bits/stdc++.h>

#define N 30105
#define ull unsigned long long

using namespace std;

ull hsi[N][250],base=233,mod=2123,hs[N];
ull pw[N];
int n,l,s,ans;
char ss[N][250];

void init(){
    pw[0]=1; 
    for(int i=1;i<=l;i++) pw[i]=pw[i-1]*base;
}//预处理进制

int main()
{
    scanf("%d%d%d",&n,&l,&s);
    for(int i=1;i<=n;i++) cin>>ss[i];
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=l;j++){
            hsi[i][j]=hsi[i][j-1]*base+ss[i][j-1];
        }
    }//求解哈希值
    for(int i=1;i<=l;i++){
        for(int j=1;j<=n;j++){
            hs[j]=hsi[j][i-1]*pw[l-i]+hsi[j][l]-hsi[j][i]*pw[l-i];
        }
        sort(hs+1,hs+1+n);
        int t=1;
        for(int j=1;j<=n;j++){
            if(hs[j]!=hs[j-1]) t=1;
            else ans+=t,++t;
        }//sort+模拟
    }cout<<ans;
    return 0;
}