ABC353E 题解

KSCD_ · 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;
}