Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- using ll = long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- using vi = vector<int>;
- const ll maxn = 3e5 + 3;
- ll now = 0;
- vl hit(maxn);
- ll dict[maxn][26];
- void insert(const string &str)
- {
- ll u = 0;
- for (auto c : str) {
- ll offset = c - 'a';
- if (dict[u][offset] == 0)
- dict[u][offset] = ++now;
- u = dict[u][offset];
- hit[u] += 1;
- }
- }
- ll get(const string &str)
- {
- ll u = 0, ret = 0;
- for (auto c : str) {
- ll offset = c - 'a';
- if (dict[u][offset] == 0)
- return ret;
- u = dict[u][offset];
- ret += hit[u];
- }
- return ret;
- }
- int main(int argc, char **argv)
- {
- ll n;
- cin >> n;
- vector<string> vs(n);
- for (auto &x : vs)
- cin >> x;
- ll ans = 0;
- for (const auto &x : vs) {
- ll v = get(x);
- dbg(x, v);
- ans += v;
- insert(x);
- }
- cout << ans << endl;
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement