C++实现前缀树（字典树） 可以用来处理查找字符串问题 例如：10w屏蔽词 替换用户违法词语成**

本文主要是介绍C++实现前缀树（字典树） 可以用来处理查找字符串问题 例如：10w屏蔽词 替换用户违法词语成**，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大佬写的前缀树详解：https://zhuanlan.zhihu.com/p/28891541
C++实现

#include <iostream>
#include<string>
#include<vector>
using namespace std;
class TrieNode{
public:
	int count;//以当前单词结尾的单词数量
	int prefix;//以该节点之前的字符串为前缀的单词数量
	vector<TrieNode*>nextNode;
	TrieNode() {
		nextNode.resize(26, nullptr);
		count = 0;
		prefix = 0;
			
	}
};
//根据字符串插入节点
void insert(TrieNode* root, string str) {
	if (root == nullptr || str.size() == 0) {
		return;
	}
	for (int i = 0; i < str.size(); i++) {
		if (root->nextNode[str[i] - 'a'] == nullptr) {
			root->nextNode[str[i] - 'a'] = new TrieNode();	
		}
		root = root->nextNode[str[i] - 'a'];
		root->prefix++;
	}
	root->count++;
}
//查找单词是否存在 存在返回数量 不存在返回-1
int search(TrieNode* root, string str) {
	if (root == nullptr || str.size() == 0) {
		return false;
	}
	for (int i = 0; i < str.size(); i++) {
		if (root->nextNode[str[i] - 'a'] == nullptr) {
			return false;
		}
		root = root->nextNode[str[i] - 'a'];
	}
	if (root->count == 0) { //有可能只是前缀 所以count==0，
		return -1;
	}
	return root->count;
}
//查找以str为前缀的单词数量
int searchPrefix(TrieNode* root, string str) {
	if (root == nullptr || str.size() == 0) {
		return 0;
	}
	for (int i = 0; i < str.size(); i++) {
		if (root->nextNode[str[i] - 'a'] == nullptr) {
			return 0;
		}
		root = root->nextNode[str[i] - 'a'];
	}
	return root->prefix;
}
int main()
{
	TrieNode* newNode = new TrieNode();
	insert(newNode, "hello");
	insert(newNode, "hello");
	insert(newNode, "hello");
	insert(newNode, "helloworld");
	cout << search(newNode, "hello") << endl;
	cout << search(newNode, "hellowo") << endl;
	cout << search(newNode, "he") << endl;
	cout << searchPrefix(newNode, "he") << endl;
	cout << searchPrefix(newNode, "hellow") << endl;
	return 0;
}

这篇关于C++实现前缀树（字典树） 可以用来处理查找字符串问题 例如：10w屏蔽词 替换用户违法词语成**的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！