[C++]白俊14426号:接頭辞の検索

12327 ワード
データ構造 白駿 木。 三輪車 テキストリンク

質問リンク


14426:接頭辞の検索

問題の概要


N個の文字列、M個の文字列を与えます.M文字列では、集合Sに含まれる少なくとも1つの接頭辞の個数を求める必要がある.

方法


簡単な答えはありましたが練習としてTrieで近づけましたすべてのN文字列をtrieに挿入し、trieからM文字列にアクセスしようとします.アクセス中にNULLノードに遭遇した場合はfalseを返し、trieから文字列の末尾に到達した場合はtrueを返します.この場合、true文字列の数を出力できます.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	Trie* node[26];

	Trie() {
		for (int i = 0; i < 26; i++) node[i] = NULL;
	}

	void insert(string& str, int idx) {
		if (idx == str.size())
			return;

		if (node[str[idx] - 'a'] == NULL)
			node[str[idx] - 'a'] = new Trie();
			
		node[str[idx] - 'a']->insert(str, idx + 1);
	}

	bool find(string& str, int idx) {
		if (idx == str.size())
			return true;

		if (node[str[idx] - 'a'] == NULL)
			return false;

		return node[str[idx] - 'a']->find(str, idx + 1);
	}

	void clear(void) {
		for (int i = 0; i < 26; i++) {
			if (node[i] != NULL) {
				node[i]->clear();
				delete node[i];
			}
		}
	}
};

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

	int n, m;
	cin >> n >> m;

	Trie* root = new Trie();

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		root->insert(str, 0);
	}

	int ans = 0;
	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;
		
		if (root->find(str, 0))
			ans++;
	}

	cout << ans << '\n';
	root->clear();
	delete root;
	return 0;
}
配列(交差OR並)
AWSリソースのパスワード等を、AWS上で管理する