题意

$nn$n 个字符串, 求两两之间的公共最长前缀的长度和

范围限制$n\le 10^{5}n\; \backslash leq\; 10^5$n≤105, 所有字符串长度和$\le 10^6\backslash leq\; 10^6$≤106

算法

朴素的暴力方法

直接按照题意实现的话需要字符串之间两两比较。

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param s string字符串一维数组 
# @return long长整型
#
class Solution:
    def solve(self , n , s ):
        r = 0
        for i in range(n):
            for j in range(i+1,n):
                l = 0
                while l < len(s[i]) and l < len(s[j]):
                    if s[i][l] != s[j][l]:
                        break
                    l+=1
                r+=l
        return r

复杂度分析

时间复杂度: 两层循环枚举两两之间进行比较，每次比较枚举前缀长度,但这里长度只有总长度限制。

按照每个字符比较的角度来看，每个字符最多比较$n-1n-1$n−1次，时间复杂度为$O(n\cdot \sum s_i)O(n\backslash cdot\; \backslash sum\{s\_i\}\; )$O(n⋅∑si​)。

所以，如果n能更小一些才能过，这里n可以取到$10^{5}10^5$105 竟然过了，但如果数据强一点应该是过不了的

空间复杂度: 只记录了结果，$O\left(1\right)O(1)$O(1)

桶排序

回想桶排序，比如拿到一组数，我们以十进制作为桶的划分

123461 123 124444 123500

我们 首先比较他们的最高位, 按照最高位分桶, 这里我们关心第6位

这样完成了按照第6位分桶

然后我们看第digit=1的桶里的，再按第5位分桶

恰好第5位都是2，全部在一起

然后我们看第digit=2的桶里的，再按第4位分桶

这时两个是3，一个是4，又分开了它们，再按第3位

然后我们看第digit=2的桶里的，再按第4位分桶

至此我们对所有数完成了分割。

接下来回顾上面的内容。

1. 第1次分割后不在一个桶里的，说明高位不同
2. 第2次分割后不在一个桶里的，说明次高位不同，而同时最高位相同
3. 第3次分割后不在一个桶里的，说明高第3位不同，而同时高第1,2位相同
4. 第4次分割后不在一个桶里的，说明高第4位不同，而同时高第1,2,3位相同

以此类推，我们不光完成分割和排序，同时在过程中知道了哪些桶之间相同的高位的长度

回到题目，虽然这里是'a'-'z'的字符串，但逻辑完全一致

以 样例为例 "niuniu","niumei","niuneng"

1. 最高位都是'n',在一个桶里
2. 高第2位都是'i',在一个桶里
3. 高第3位都是'u',在一个桶里
4. 高第4位把"niumei" 单独分到了'm'桶里，而另外两个在'n'桶里，这说明'n'桶和'm'桶的公共前缀长度是 $4-1=34-1=3$4−1=3
5. 高第5位把"niuniu" 和 "niuneng" 分别分到'i'和'e'桶，这说明这两个桶的公共前缀长度是 $5-1=45-1=4$5−1=4

贡献

当出现了分到不同的桶，要计算两两桶之间的贡献，那么可以用前缀和

sum += 之前桶里元素个数和 * 当前桶元素个数 * 公共长度

之前桶里元素个数和 += 当前桶元素个数

这里需要特别注意的是，字符串长度可能短于分割时的，不像数字可以高位认为是零，而且还可能访问到意外的内存。

所以注意对字符串的长度判断和处理：多个相同的字符串之间的公共长度是它们自身，这块贡献是$\frac{个数\cdot (个数-1)}{2}\cdot 公共长度\backslash frac\{个数\; \backslash cdot\; (个数-1)\}\{2\}\backslash cdot\; 公共长度$2个数⋅(个数−1)​⋅公共长度

以上就完成了题目

代码

class Solution {
public:
    long long f(int chidx,vector<string *>& sref){
        vector<vector<string *> > alphabet(27,vector<string *>()); // [26] 表示 长度刚好是 chidx的
        for(auto sitr:sref){
            if(sitr->size() == chidx){
                alphabet[26].push_back(sitr);
            }else{
                alphabet[(*sitr)[chidx]-'a'].push_back(sitr);
            }
        }
        long long result = 0;
        long long precnt = 0;
        for(int ch =0;ch<27;ch++){
            result += precnt * alphabet[ch].size() * chidx;
            precnt += alphabet[ch].size();
        }
        // 长度刚好为 chidx，且前chidx个一样
        result += alphabet[26].size() * ((long long)alphabet[26].size()-1)/2 * chidx;
        for(int ch=0;ch<26;ch++){
            if(alphabet[ch].size() < 2)continue;
            result += f(chidx+1,alphabet[ch]);
        }
        return result;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return long长整型
     */
    long long solve(int n, vector<string>& s) {
        vector<string *> sref = {};
        for(int i =0;i<n;i++){
            sref.push_back(&s[i]);
        }
        return f(0,sref);
    }
};

复杂度分析

时间复杂度: 初始化会建立字符串指针数组。我们在函数的第$ii$i层，对当前桶内的每一个字符串的第$ii$i位进行分割到桶，桶的个数是$26+1=2726+1=27$26+1=27个,常数个，也就是我们总的遍历的是所有字符串的每一位1次,所以复杂度是$O(n+\sum S_i)O(n+\backslash sum\; S\_i)$O(n+∑Si​)

空间复杂度: 顶层建立了n个桶，每一次函数调用有初始化的27个桶，因为每多一个长度会多一次调用，同一位上字符不同会多一次调用，所有层被调用的次数不大于所有字符串字符数，每一次判断第i个字符串的第j个字符就会发生一次分桶，也就是把指针放进桶里的操作，所以总次数也是所有字符串的字符数量和。所以总空间复杂度$O(n+\sum S_i)O(n+\backslash sum\; S\_i)$O(n+∑Si​)

知识点

1. 使用指针或下标来分类s而不是复制s，这样每次只有常数的排序代价。