前缀树，trie树
2024-09-03 06:34:11
前缀树：
假设一个字符串数组，“abcd”,"bcd","gef" , 构建一颗树，字母是在路径上，节点上最基本的存储的信息包括：
以这个节点结尾的 字符串的数量；
经过这个节点的字符串的数量；
一个字符串类型的数组arr1，另一个字符串类型的数组arr2；
（1）arr2中有哪些字符，是arr1中出现的？请打印
（2）arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请 打印
（3）arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀
package my_basic.class_7;
public class Code_00_TrieTree {
//前缀树
public static class TrieNode{
public int end;
public int path;
public TrieNode[] nexts;
public TrieNode() {
end = 0;
path = 0;
nexts = new TrieNode[26]; //之前没写 空指针
}
}
public static class Trie{
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
int index = 0;
TrieNode node = root;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.path++;
}
node.end++;
}
public int search(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
int index = 0;
TrieNode node = root;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}
public void delete(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
int index = 0;
TrieNode node = root;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].path == 0) {
node.nexts[index] = null; //后面的节点直接删去
return;
}
node = node.nexts[index];
}
node.end--;
}
public int prefixNumber(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
int index = 1;
TrieNode node = root;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.path;
}
}
public static void main(String[] args) {
String[] arr1 = {"abc","bcd","def","bcf"};
String[] arr2 = {"b","a","bc"};
Trie trie = new Trie();
for (int i = 0; i < arr1.length; i++) {
trie.insert(arr1[i]);
}
//arr2中有哪些字符，是arr1中出现的
for (int i = 0; i < arr2.length; i++) {
if (trie.search(arr2[i]) != 0) {
System.out.print(arr2[i] + " ");
}
}
System.out.println(" ");
System.out.println("===================================");
//arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？
for (int i = 0; i < arr2.length; i++) {
if (trie.prefixNumber(arr2[i]) != 0) {
System.out.print(arr2[i] + " ");
}
}
System.out.println(" ");
System.out.println("===================================");
String res = null;
int pre = 0;
for (int i = 0; i < arr2.length; i++) {
int prefixNum = trie.prefixNumber(arr2[i]);
if (prefixNum != 0) {
System.out.print(arr2[i] + " ");
if(prefixNum >= pre) {
res = arr2[i];
pre = prefixNum;
}
}
}
System.out.println();
System.out.println(res);
// Trie trie = new Trie();
// System.out.println(trie.search("zuo"));
// trie.insert("zuo");
// System.out.println(trie.search("zuo"));
// trie.delete("zuo");
// System.out.println(trie.search("zuo"));
// trie.insert("zuo");
// trie.insert("zuo");
// trie.delete("zuo");
// System.out.println(trie.search("zuo"));
// trie.delete("zuo");
// System.out.println(trie.search("zuo"));
// trie.insert("zuoa");
// trie.insert("zuoac");
// trie.insert("zuoab");
// trie.insert("zuoad");
// trie.delete("zuoa");
// System.out.println(trie.search("zuoa"));
// System.out.println(trie.prefixNumber("zuo"));
}
}
最新文章
- C#----对时间结构DateTime的使用(时间日期的使用)
- 用Access作为后台数据库支撑。
- Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition)
- iOS NSNotification的使用
- Using GET_GROUP_SELECTION For Record Groups in Oracle Forms
- java异常处理的两种方法
- [51NOD1127]最短的包含字符串（尺取法）
- CPU卡及NFC供应商
- spring的主要特性
- Android 动画之RotateAnimation应用详解
- 转：基于开源项目OpenCV的人脸识别Demo版整理（不仅可以识别人脸，还可以识别眼睛鼻子嘴等）【模式识别中的翘楚】
- httrack,webdup,WinHTTrack,WebZip
- printdir-deldir-bmp
- POJ 2253 Frogger floyd算法
- 【CentOS】阿里云ECS申请CA证书配置SSL
- 为什么PPIO要设计支付代理节点？
- [Linux]Ubuntu 16.04 远程桌面
- 关于Socket.IO的知识点记录
- 当一个HTML元素需要添加mouseon、mouseout与click事件，或者mouserenter、mouseleave和click事件时，click事件无法触发
- Codeforce 733B - Parade （枚举）