【題解】Zerojudge a080 - NOI2000 Day2.1.单词查找树

題目連結

題目大意

給定一堆字串，請建構其字典樹，並輸出字典樹節點的數量。

題解

在寫本題的時候用了 vector 搭配偽指標結果一直吃 RE，後來改成先 reserve(200000) 後才 AC。估計是因為 vector 在倍增空間的時候一次要搬 $26n$ 個元素太花費空間，預先開出空間就沒事了。因為直接用指標寫比較簡潔，底下的程式碼是用指標實作。

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

struct Node {
	Node* go[26] = {};
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Node* root = new Node();
	int ans = 1;
	string s;
	while(cin >> s) {
		Node* p = root;
		for(char c : s) {
			int v = c - 'A';
			if(p->go[v] == nullptr) {
				p->go[v] = new Node();
				ans++;
			}
			p = p->go[v];
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a080 - NOI2000 Day2.1.单词查找树