相似和

最优解

我们只需要知道，对于每个字符串，它的每个前缀在前面的字符串中出现了几次。
然后我们按每一位的字母的贡献算，第i位的字母对答案的贡献为的前位作为前缀在前面的字符串中出现了几次。
所以我们可以建立字典树去统计和查询字符串前缀的信息。
空间复杂度和时间复杂度都是

int ch[1000005][26];
int sz[1000005];
long long solve(int n, vector<string> s){
    long long ans = 0;
    int tot = 0; int rt = ++tot;
    memset(ch[rt], 0, sizeof ch[rt]); sz[rt] = 0;
    for(int i = 0; i < n; ++i){
        int p = rt;
        for(int j = 0; j < s[i].size(); ++j){
            int x = s[i][j] - 'a';
            if(ch[p][x]) {
                p = ch[p][x];
                ans += sz[p];
            }
            else{
                p = -1; break;
            }
        }
        p = rt;
        for(int j = 0; j < s[i].size(); ++j){
            int x = s[i][j] - 'a';
            if(!ch[p][x]) {
                ch[p][x] = ++tot; memset(ch[tot], 0, sizeof ch[tot]); sz[tot] = 0;
            }
            p = ch[p][x]; sz[p]++;
        }
    }return ans;
}