[洛谷 4503][CTSC2014]企鹅QQ

题目链接

https://www.luogu.org/problem/P4503

题解

考虑字符串哈希。

我们分别递推出每个字符串的前缀和后缀的哈希值。每次枚举中间断开的位置，把前后两段拼接起来计算新串的哈希值。

使用 map 或者 sort 就可以统计答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define BIG1 19260817
#define BIG2 19491001
using namespace std;
char str[205];
unsigned long long f[30005][205],g[30005][205],tmp[30005];
int main()
{
 int n,l,s,ans=0;
 scanf("%d%d%d",&n,&l,&s);
 for(int i=1;i<=n;i++)
 {
  scanf("%s",str+1);
  for(int j=1;j<=l;j++)
   f[i][j]=f[i][j-1]*BIG1+str[j];
  for(int j=l;j>=1;j--)
   g[i][j]=g[i][j+1]*BIG2+str[j];
 }
 for(int i=1;i<=l;i++)
 {
  for(int j=1;j<=n;j++)
   tmp[j]=f[j][i-1]*233+g[j][i+1]*323;
  sort(tmp+1,tmp+n+1);
  int num=1;
  for(int j=2;j<=n;j++)
  {
   if(tmp[j]==tmp[j-1])ans+=num,num++;
   else num=1;
  }
 }
 printf("%d\n",ans);
 return 0;
}