浏览 1572 次
锁定老帖子 主题:过滤黑名单
精华帖 (0) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-03-09
一个树,每个节点有个hashmap,一个iskeyword,通过isKeyWord来判断是否关键字,如果不是通过hashmap向下找寻,如果hashmap找不到,从root节点重新找 import java.util.*; public class Trie { private Vertex root; public static void main(String[] args){ Trie t = new Trie(); t.addWord("中"); t.addWord("中华"); t.addWord("中华人"); t.addWord("胡"); System.out.println(t.isExistWords("啊uhfgdigdfg时发生大幅度上升的方式的答复 ")); System.out.println(t.isExistWords("中啊uhfgdigdfg时发生大幅度上升的方式的答复 ")); System.out.println(t.isExistWords("胡啊uhfgdigdfg时发生大幅度上升的方式的答复 ")); } protected class Vertex { protected String value; protected boolean isKeyWord; protected Map edges; Vertex(String value,boolean inital) { isKeyWord = false; this.value = value; if(inital) edges = new HashMap(); } } public Trie () { root = new Vertex("root",true); } public boolean isExistWords(String word) { return isExistWords(root, word); } private boolean isExistWords(Vertex vertex, String wordSegment) { if(vertex.isKeyWord) return true; if (wordSegment.length() == 0) { if(!vertex.isKeyWord) return false; } char c = wordSegment.charAt(0); Vertex v = (Vertex) vertex.edges.get(String.valueOf(c)); if (v == null) { return isExistWords(root, wordSegment.substring(1)); } else { return isExistWords(v, wordSegment.substring(1)); } } public void addWord(String word) { addWord(root, word); } private void addWord(Vertex vertex, String word) { if (word.length() != 0) { char c = word.charAt(0); Vertex v = new Vertex(String.valueOf(c),false); if (!vertex.edges.keySet().contains(String.valueOf(c))) { v.edges = new HashMap(); vertex.edges.put(String.valueOf(c), v); }else{ v = (Vertex) vertex.edges.get(String.valueOf(c)); } addWord(v, word.substring(1)); }else{ vertex.isKeyWord = true; } } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |