C++14(g++5.4) 解法, 执行用时: 173ms, 内存消耗: 52528K, 提交时间: 2019-12-10 00:44:41

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 510000;

struct Node {
  int cnt;
  int val;
  vector<int> ch;
  vector<pair<int, int>> chs;
};
Node nodes[MAXN];
int sz;
int cost;

void insert(string s) {
  int cur = 0;
  for (auto ch: s) {
    int id = ch - 'a';
    if (nodes[cur].ch.size() == 0) nodes[cur].ch.resize(26);
    int &nxt = nodes[cur].ch[id];
    if (nxt == 0) nxt = ++sz;
    nodes[nxt].cnt++;
    cur = nxt;
  }
  nodes[cur].val++;
}
void dfs1(int cur, int p) {
  if (nodes[cur].val) {
    nodes[p].chs.push_back({nodes[cur].cnt, cur});
    p = cur;
  }
  if (nodes[cur].ch.size() == 0) return;
  for (int i = 0; i < 26; i++) {
    int nxt = nodes[cur].ch[i];
    if (nxt == 0) continue;
    dfs1(nxt, p);
  }
}
int id;
long long dfs2(int cur, int fa) {
  int cid = id++;
  long long tot = cid - fa;
  sort(nodes[cur].chs.begin(), nodes[cur].chs.end());
  for (auto it: nodes[cur].chs) tot += dfs2(it.second, cid);
  return tot;
}

int main(){
  int n; cin >> n;
  while (n--) {
    string s; cin >> s;
    reverse(s.begin(), s.end());
    insert(s);
  }
  dfs1(0, 0);
  cout << dfs2(0, 0) << endl;
  return 0;
}

C++ 解法, 执行用时: 69ms, 内存消耗: 35320K, 提交时间: 2021-12-12 08:45:38

#include<bits/stdc++.h>
using namespace std;
struct node{
	string str;
	int len,s;
	vector <int> a;
}a[100001];
int trie[510001][26],f[510001],id[100001],tot;
long long ans;
bool cmp1(const node &x,const node &y){
	return x.len < y.len;
}
bool cmp2(const int &x,const int &y){
	return a[x].s < a[y].s;
}
void func(int i){
	id[i] = tot++;
	for (int j = 0;j < a[i].a.size();j++){
		ans += tot - id[i];
		func(a[i].a[j]);
	}
}
int main(){
	int n,t,temp,*p,i,j;
	cin>>n;
	for (i = 1;i <= n;i++){
		cin>>a[i].str;
		a[i].len = a[i].str.length();
		a[i].s = 0;
	}
	sort(a + 1,a + 1 + n,cmp1);
	for (i = 1;i <= n;i++){
		t = 0;
		temp = 0;
		for (j = a[i].len;j--;){
			p = &trie[t][a[i].str[j] - 'a'];
			if (!*p)*p = ++tot;
			t = *p;
			if (f[t]){
				temp = f[t];
				a[temp].s++;
			}
		}
		f[t] = i;
		a[temp].a.push_back(i);
	}
	for (i = 0;i <= n;i++)
		sort(a[i].a.begin(),a[i].a.end(),cmp2);
	tot = 0;
	func(0);
	cout<<ans;
	return 0;
}