bzoj 3555: [Ctsc2014]企鹅QQ

题意：

时间复杂度：O(n*l)

难度：NOIP

题解：我们计算出每个字符串，删除第i个点时的hash值，然后排序，找到hash值相等的有几个，再统计答案即可！

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#define ull unsigned long long
#define ll long long
#define N 10005
#define seed 1313131
using namespace std;
ull sed[205],has[30000*200+5];
char str[205];//注意数组的大小！！！ 
int tot;
int main()
{
	int n,l,s;
	scanf("%d%d%d",&n,&l,&s);
	sed[0]=1,sed[1]=1;
	for(int i = 1;i <= 205;i++)
	{
		sed[i]=sed[i-1]*seed;
	}
	for(int i = 1;i <= n;i++)
	{
		scanf("%s",str);
		ull hass=0;
		for(int j = 0;j < l;j++)
		{
			hass=hass*seed+str[j];
		}
		for(int j = 0;j < l;j++)
		{
			has[++tot]=hass-sed[l-j-1]*str[j];
		}
	}
	sort(has+1,has+1+tot);
	int cnt=1;//注意  初值要赋1！！！，由于数据较水，赋成0也能AC 
	ll ans=0;
	for(int i = 1;i < tot;i++)
	{
		if(has[i]==has[i+1])
		{
			cnt++;
		}else
		{
			ans+=cnt*(cnt-1)/2;
			cnt=1;
		}
	}
	ans+=cnt*(cnt-1)/2;
	printf("%lld\n",ans);
	return 0;
}