Submission #15801395

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long LL;

const int MAXN = 2e5 + 10, MAXL = 1e6 + 10;

int n;
int tmp[30];
std::string s[MAXN];

template <int N, int S>
struct Trie {
	int tot;
	int ed[N], ch[N][S];
	inline void insert(const std::string &s) {
		int u = 0;
		for (const auto &cur: s) {
			int v = cur - 'a';
			if (!ch[u][v]) ch[u][v] = ++tot;
			u = ch[u][v];
		}
		++ed[u];
	}
};
Trie <MAXL, 26> T;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cin >> n;
	for (int i = 1; i <= n; ++i) {
		std::cin >> s[i];
		std::reverse(s[i].begin(), s[i].end());
		T.insert(s[i]);
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 26; ++j) tmp[j] = 0;
		for (const auto &cur: s[i]) ++tmp[cur - 'a'];
		int u = 0;
		for (const auto &cur: s[i]) {
			int v = cur - 'a';
			for (int j = 0; j < 26; ++j) tmp[j] && T.ch[u][j] && (ans += T.ed[T.ch[u][j]]);
			--tmp[v], u = T.ch[u][v];
		}
	}
	std::cout << ans - n << '\n';
	return 0;
}

Submission Info

Judge Result