【洛谷P4503】企鹅QQ【字符串hash】

题目大意：

题目链接：https://www.luogu.org/problem/P4503
若两个字符串长度相同且不超过一处字符不同，则称这两个字符串相似。求$n$个长度相同的字符串相似的对数。

---

思路：

由于题目中要求不超过一处不同，所以我们可以考虑枚举两个字符串哪里不相同，然后判断前后是否完全一致即可。
判断两个字符串是否一致直接用字符串$hash$就可以了。
那么对于每一个字符串，我们枚举它的每一位，从前往后做一遍$hash$，然后再从后往前做一遍$hash$。这样我们再枚举每一位，用第三个$hash$记录前后是否相同。只需要给前后的两个$hash$值再一个特征值即可。这个特征值重复概率极小，随便取一个即可。
然后我们将第三个$hash$值排序，然后用双指针，每次找到一段连续的相同区间，用等差数列求和公式求一下方案数即可。
时间复杂度$O(nmlog(nm))$。其中$m$表示字符串长度。

---

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;

const int N=30010,M=210;
const ull base=13331;
ull hash1[N][M],hash2[N][M],hash[N*M],ans;
int n,m,WYC_AK_IOI,cnt;
char ch[N][M];

int main()
{
	scanf("%d%d%d
",&n,&m,&WYC_AK_IOI);
	for (int i=1;i<=n;i++)
	{
		cin>>ch[i]+1;
		for (int j=1;j<=m;j++)
			hash1[i][j]=hash1[i][j-1]*base+(ull)ch[i][j];
		for (int j=m;j>=1;j--)
			hash2[i][j]=hash2[i][j+1]*base+(ull)ch[i][j];
		for (int j=1;j<=m;j++)
			hash[++cnt]=hash1[i][j-1]*131ull+hash2[i][j+1]*139ull;
	}
	sort(hash+1,hash+1+cnt);
	for (ull l=1,r=2;r<=cnt+1;r++)
		if (hash[r]!=hash[r-1])
		{
			ull n=r-l;
			ans+=n*(n-1)/2;
			l=r;
		}
	cout<<ans;
	return 0;
}