Trie - PREFIX

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 1 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một xâu được gọi là xâu tiền tố của một xâu khác nếu nó xuất hiện ở vị trí đầu tiên của xâu này.

Ví dụ xâu ab là tiền tố của xâu abcd; aa là tiền tố của aa

Yêu cầu: Cho \(n\) xâu ký tự, hãy đếm số cặp xâu mà xâu này là tiền tố của xâu còn lại

Input

  • Dòng đầu tiên ghi số nguyên dương \(n\ (1\le n\le 10^6)\)
  • \(n\) dòng tiếp theo, mỗi dòng ghi một xâu ký tự chỉ gồm các chữ cái tiếng Anh in thường với độ dài của mỗi xâu không vượt quá \(10\)

Output

  • In ra một số nguyên duy nhất là số lượng xâu tìm được.

Example

Test 1

Input 
4
abc
aa
aab
aa
Output 
3

Bình luận


  • 0
    admin2    12:54 p.m. 17 Tháng 5, 2023

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    define db double

    define pll pair<ll, ll>

    define str string

    define pii pair<int, int>

    define vpii vector<pii>

    define vl vector<ll>

    define vpll vector<pll>

    define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

    define mp make_pair

    define sz(x) x.size()

    define fi first

    define pb push_back

    define se second

    define sqr(i) i * i

    define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))

    define turn_on(i, m) (m |= (1LL << i))

    define turn_off(i, m) (m &= ~(1LL << i))

    define MASK(i) (1ll << (i))

    define BIT(x, i) (((x) >> (i)) & 1)

    // x << y : x * (2 ^ y)
    // x >> y : x / (2 ^ y)
    // (((x) >> i) & 1) : lay ra bit thu i cua x
    // (m |= (1LL << i)) : bat bit thu i cua m len
    // (m &= ~(1LL << i)) : tat bit thu i cua m
    // __builtin_clz(n)) : dem so luong so 0 dung dau
    // __builtin_ctz(n)) : dem so luong so 0 dung cuoi
    // __builtin_popcount(n) : dem so luong so 1 trong bit
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    const int MAXN = 2e5 + 1;
    const int LOG = 17;
    const ll MOD = 1e9 + 7;
    const ll INF = 1e18;

    struct TrieNode {
    TrieNode* child[26];
    int cnt;
    TrieNode() {
    for(int i = 0; i < 26; i++)
    child[i] = NULL;
    cnt = 0;
    }
    };

    TrieNode* root = new TrieNode();

    void TrieInsert(const string &s) {
    int n = s.size();
    TrieNode* p = root;
    for(int i = 0; i < n; i++) {
    int nxt = s[i] - 'a';
    if(p->child[nxt] == NULL)
    p->child[nxt] = new TrieNode();
    p = p->child[nxt];
    p->cnt++;
    }
    }

    bool TrieFind(const string &s) {
    int n = s.size();
    TrieNode* p = root;
    for(int i = 0; i < n; i++) {
    int nxt = s[i] - 'a';
    if(p->child[nxt] == NULL)
    return false;
    p = p->child[nxt];
    }
    return p->cnt>0;
    }

    void solve(){
    ll n;
    cin >> n;
    vector<string> arr;
    for(int i = 0; i < n; i++) {
    str s;
    cin >> s;
    arr.pb(s);
    }
    sort(arr.begin(), arr.end());
    reverse(arr.begin(), arr.end());
    ll ans = 0;
    map<string, ll> cnt;
    for(int i = 0; i < n; i++) {
    if(TrieFind(arr[i])) {
    TrieNode* p = root;
    bool ok = true;
    for(int j = 0; j < arr[i].size(); j++) {
    int nxt = arr[i][j] - 'a';
    if(p->child[nxt] == NULL) {
    ok = false;
    break;
    }
    p = p->child[nxt];
    }
    if(!ok) {
    TrieInsert(arr[i]);
    continue;
    }
    ans += p -> cnt;
    }
    TrieInsert(arr[i]);
    }
    cout << ans << '\n';
    }

    int main(){
    IOS;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    // #else
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    #endif
    solve();
    }