字符串哈希
对于两个字符串 \(s,t\)，如果要判断其是否相等，则需要分别比较每一个字符。而使用哈希函数将字符串映射可以更方便地完成判断。
有哈希函数 \(f(s)\)，我们希望：
- 当 \(f(s)\neq f(t)\) 时，\(s\neq t\)。
- 当 \(f(s)=f(t)\) 时，\(s\) 可能等于 \(t\)，也可能不相等。我们希望他们相等，而不相等的情况称为哈希冲突。
我们要做的就是构造一个哈希函数，使得哈希冲突最好没有。这样我们就能通过比较两个字符串的哈希值准确判断相等。
通常我们采用多项式哈希（进制哈希）的方式。我们定义一个基底 \(base\)（通常是质数），然后把原字符串转为一个 \(base\) 进制数，再对其取模一个大数（需要与 \(base\) 互质，因此常用一些大质数，如 \(998244353\)、\(10^9+7\)、\(1222827239\)、\(212370440130137957\)，也可以用 unsigned long long 自然溢出的方法，相当于取模 \(2^{64}\) 以此扩大模数），最终得到哈希值。
const int base=233;
const int p=998244353;
int hash(string s){int res=0;for(int i=0;i<s.size();i++){res=(1ll*res*base+s[i])%p;}return res;
}
单个模数的哈希容易产生冲突，我们可以对多个数取模得到多个哈希值，然后分别比较是否相等，这样值域就扩大到了两模数的乘积。一般来说两个模数就已足够（目前暂无卡确定模数的双哈希的方法）。
子串哈希
多次询问一个字符串子串的哈希，每次计算哈希值复杂度与暴力没有区别。
于是我们可以对字符串预处理出每个前缀的哈希，用类似前缀和的思想求出子串哈希。
根据进制哈希的计算方法，我们有 \(s\) 长度为 \(i\) 的前缀子串的哈希 \(f_i(s)=s[1]\cdot base^{i-1}+s[2]\cdot base^{i-2}+\cdots+s[i-1]\cdot base+s[i]\)。那么 \(s[l..r]\) 的哈希为 \(f(s[l..r])=f_r(s)-f_{l-1}(s)\times b^{r-l+1}\)。预处理 \(b^{r-l+1}\) 即可在 \(O(1)\) 求得。
Luogu P4503 [CTSC2014] 企鹅 QQ
想一下怎么枚举。首先你不可能枚举两两字符串对，去比较他们是不是只差一个。这样肯定是不对的。
然后你就得换一个维度考虑，去枚举那个不相同的字符。
假设这个字符出现在第 \(i\) 位，那么可以构成相似字符串对的两个串，必须在删掉第 \(i\) 位之后完全相同。
这时候我们就可以用子串哈希去求一下每个串删掉第 \(i\) 位后的哈希值。具体来说就是求出 \(s[1..i-1]\) 和 \(s[i+1..L]\) 的哈希值，把前面串的值 \(\times b^{L-i}\) 再加上后面串的值，拼起来就是整个的哈希值。求出来以后把他们放一块排序，看看有多少组相同串。对于一组总共有 \(k\) 个相同串的组，其对答案的贡献为 \(k\times(k-1)\div2\)。
这样时间复杂度是 \(O(LN\log N)\)，可以通过。
为了防止被卡写了双哈希。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e4+10;
const int base=233;
const int MOD1=998244353;
const int MOD2=1e9+7;
int n,L,S,ans;
int pob1[N],pob2[N];
string s[N];
struct Node{int hs1,hs2;
}hs[N][210],a[N];
int calc1(int pos,int l,int r){if(l>r) return 0;return (hs[pos][r].hs1-hs[pos][l-1].hs1*pob1[r-l+1]%MOD1+MOD1)%MOD1;
}
int calc2(int pos,int l,int r){if(l>r) return 0;return (hs[pos][r].hs2-hs[pos][l-1].hs2*pob2[r-l+1]%MOD2+MOD2)%MOD2;
}
bool cmp(Node x,Node y){if(x.hs1==y.hs1) return x.hs2<y.hs2;else return x.hs1<y.hs1;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>L>>S;pob1[0]=pob2[0]=1;for(int i=1;i<=n;i++){s[i]=" ";for(int j=1;j<=L;j++){char c;cin>>c;s[i]+=c;hs[i][j].hs1=(hs[i][j-1].hs1*base+s[i][j])%MOD1;hs[i][j].hs2=(hs[i][j-1].hs2*base+s[i][j])%MOD2;}}for(int i=1;i<=L;i++){pob1[i]=(pob1[i-1]*base)%MOD1;pob2[i]=(pob2[i-1]*base)%MOD2;} for(int i=1;i<=L;i++){for(int j=1;j<=n;j++){a[j].hs1=(calc1(j,1,i-1)*pob1[L-i]%MOD1+calc1(j,i+1,L))%MOD1;a[j].hs2=(calc2(j,1,i-1)*pob2[L-i]%MOD2+calc2(j,i+1,L))%MOD2;}sort(a+1,a+1+n,cmp);int cnt=0,l=1,r=1;while(l<=n&&r<=n){while(r<=n&&a[r].hs1==a[l].hs1&&a[r].hs2==a[l].hs2) r++;cnt=r-l;ans+=cnt*(cnt-1)/2;l=r;}}cout<<ans;return 0;
}