Hướng giải của Đếm tiền tố bằng Trie

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Đếm tiền tố bằng Trie

Phân tích

Trong Trie, mỗi node lưu:

  • cnt: số xâu "không phải chính node đó" đi qua.
  • endCnt: số xâu kết thúc tại node này.

Khi muốn đếm số xâu khác có xâu hiện tại làm tiền tố, ta tìm node tương ứng với xâu, kết quả là cnt (đã trừ chính xâu đó).

Độ phức tạp

  • Thời gian: O(tổng độ dài các xâu)
  • Không gian: O(tổng độ dài × 26)

Code mẫu C++

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

struct TrieNode {
    TrieNode* child[26];
    int cnt;       // So xau di qua (bao gom chinh no neu no den day)
    int endCnt;    // So xau ket thuc tai day
    TrieNode() : cnt(0), endCnt(0) {
        fill(child, child + 26, nullptr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<string> words(n);
    TrieNode* root = new TrieNode();

    // Them tat ca xau vao Trie
    for (int i = 0; i < n; i++) {
        cin >> words[i];
        TrieNode* cur = root;
        for (char c : words[i]) {
            int idx = c - 'a';
            if (!cur->child[idx]) cur->child[idx] = new TrieNode();
            cur = cur->child[idx];
            cur->cnt++;  // Tang cho moi xau di qua
        }
        cur->endCnt++;  // Dem xau ket thuc tai day
    }

    // Voi moi xau, dem so xau khac ma no la tien to
    for (int i = 0; i < n; i++) {
        TrieNode* cur = root;
        for (char c : words[i]) {
            cur = cur->child[c - 'a'];
        }
        // So xau khac co tien to la words[i] = cnt - endCnt
        // (tru di chinh nhung xau giong y het words[i])
        cout << cur->cnt - cur->endCnt << endl;
    }
    return 0;
}

Giải thích

  • Mỗi khi thêm một xâu, mọi node trên đường đi của nó được cộng cnt.
  • endCnt cho biết có bao nhiêu xâu kết thúc tại node đó (giống xâu hiện tại).
  • Khi cần đếm tiền tố cho xâu w: đi tới node tương ứng với w, kết quả là cnt - endCnt (vì endCnt xâu khác cũng đếm nhưng giống hệt và không phải "xâu khác mà w là tiền tố").

Nhận xét

Không có ý kiến tại thời điểm này.