本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-12 09:32:10

题意

给出 $n$ 个字符串，求这些字符串两两之间最长公共前缀长度的和。

思路

暴力地两两计算显然会超时，需要优化。

考虑按位求解。按照当前位之前的位全部一致的要求分组。因此在每一组中，若当前位某一字母有 $k$ 个且 $k>1$，则会产生 $\frac{k(k-1)}{2}$ 的贡献。

为了接着处理后面的位，要在处理时把还没处理完的字符串按照这一位的值分组，处理完这一位后再分组处理下一位。

如此，若设字符串总长度为 $S$，由于每一位只会被处理一次，时间复杂度为 $O(S)$。

具体看代码实现。

代码

#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=3e5+10;
int n,ans;
string s[N];
vector <int> st;\/\/初始的组，包含所有字符串 
void sol(vector <int> &sg,int pos)
{
	vector <int> ts[27];
	int c[27];
	for(int i=0;i<26;i++) c[i]=0;
	for(int k:sg)
	{
		int id=s[k][pos]-'a';
		c[id]++;
		if(s[k].size()>pos+1) ts[id].push_back(k);\/\/只有这一位相同，才可能继续在同一组 
	}\/\/处理这一组中的所有字符串 
	for(int i=0;i<26;i++) if(c[i]>1)
	{
		ans+=c[i]*(c[i]-1)\/2;\/\/处理贡献 
		if(ts[i].size()>1) sol(ts[i],pos+1);\/\/继续处理下一位 
	} 
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],st.push_back(i); 
	sol(st,0);
	cout<<ans;
	return 0;
}