[CTSC2014]企鹅QQ

字符串 哈希

题面

给出$n$个长度为$L$的字符串。问有多少对字符串去掉同一位后完全相同？

• $n\leq30000,L\leq200$

解析

显然的$O(nlognL^2)$暴力。
（$O(L)$枚举去掉的位置，$O(nlognL)$字符串排序）
可以发现有很多复杂度摊在了字符串的比较上。
字符串的比较可以通过字符串哈希转化为数字的比较，优化掉$O(L)$的复杂度。
具体哈希方法多样：

• 可以像我一样，用异或和计算哈希值，枚举到删掉某一位时直接异或掉该位哈希值。
• 可以像$hzwer$一样，分别计算出前缀后缀哈希值，枚举到删掉某一位时直接 该位前的前缀哈希值 和 该位后的后缀哈希值 相乘。

复杂度都为$O(L*nlogn)$
注意事项：

• $Base$设的尽量大，几百都没关系。
• $Hash$值应该预处理出来，而不是在线运算。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int n,l,s;
ll Hash[40000],Hash1[40000],B[40000],ans;
char a[40000][300];
int main()
{
  scanf("%d%d%d",&n,&l,&s);
  fp(i,1,n) scanf("%s",a[i]+1);
  B[0]=1;B[1]=359;fp(i,2,l) B[i]=B[i-1]*359;
  fp(i,1,n)
    fp(j,1,l)
    Hash[i]^=(a[i][j]*B[j-1]),Hash1[i]=Hash[i];
  fp(i,1,l)
    {
      fp(j,1,n) Hash[j]=Hash1[j],Hash[j]^=(a[j][i]*B[i-1]);
      sort(Hash+1,Hash+n+1);re int now=1;
      fp(j,2,n) if(Hash[j]==Hash[j-1]) ans+=now,++now;
      else now=1;
    }
  printf("%lld\n",ans);
  return 0;
}