[关闭]
@ysner 2018-06-09T12:21:04.000000Z 字数 1004 阅读 1742

[CTSC2014]企鹅QQ

字符串 哈希


题面

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

解析

显然的暴力。
枚举去掉的位置,字符串排序)
可以发现有很多复杂度摊在了字符串的比较上。
字符串的比较可以通过字符串哈希转化为数字的比较,优化掉的复杂度。
具体哈希方法多样:

复杂度都为
注意事项:

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll unsigned long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. int n,l,s;
  14. ll Hash[40000],Hash1[40000],B[40000],ans;
  15. char a[40000][300];
  16. int main()
  17. {
  18. scanf("%d%d%d",&n,&l,&s);
  19. fp(i,1,n) scanf("%s",a[i]+1);
  20. B[0]=1;B[1]=359;fp(i,2,l) B[i]=B[i-1]*359;
  21. fp(i,1,n)
  22. fp(j,1,l)
  23. Hash[i]^=(a[i][j]*B[j-1]),Hash1[i]=Hash[i];
  24. fp(i,1,l)
  25. {
  26. fp(j,1,n) Hash[j]=Hash1[j],Hash[j]^=(a[j][i]*B[i-1]);
  27. sort(Hash+1,Hash+n+1);re int now=1;
  28. fp(j,2,n) if(Hash[j]==Hash[j-1]) ans+=now,++now;
  29. else now=1;
  30. }
  31. printf("%lld\n",ans);
  32. return 0;
  33. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注