Submission #53405355

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int K = 26;
struct Vertex {
    int next[K];
    int count = 0;
    bool output = false;

    Vertex() { fill(begin(next), end(next), -1); }
};

vector<Vertex> trie(1);

void add_string(string &s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
        trie[v].count++;
    }
    trie[v].output = true;
}

int count_prefix_match(string &s) {
    int v = 0, res = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            return res;
        }
        v = trie[v].next[c];
        res += trie[v].count;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;

    long long ans = 0;
    for (int zz = 0; zz < n; zz++) {
        string str;
        cin >> str;
        ans += count_prefix_match(str);
        add_string(str);
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Judge Result