考虑拆贡献。
显然答案可以拆成对于所有 \(s_i\) 的每一个后缀的反串，作为前缀在所有串中的出现次数的加和。
这个东西字典树维护一下就行了。
不知道是谁考场上写哈希赛后被人对着模数卡掉了
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
constexpr int N = 1e6 + 10;
int n, tot, cnt[N], t[N][26];
long long ans; string s[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
FL(i, 1, n) cin >> s[i], ans += 2ll * n * s[i].size();
FL(i, 1, n){
int p = 0, l = s[i].size();
FR(j, l - 1, 0){
if(!t[p][s[i][j] - 'a']) t[p][s[i][j] - 'a'] = ++tot;
++cnt[p = t[p][s[i][j] - 'a']];
}
}
FL(i, 1, n){
int p = 0, l = s[i].size();
FL(j, 0, l - 1){
if(!t[p][s[i][j] - 'a']) break;
ans -= cnt[p = t[p][s[i][j] - 'a']] * 2;
}
}
cout << ans << endl;
return 0;
}