内容简介:Trie树,又称为前缀树或字符串树,我这里只是简单讲述一下Trie树,如果需要深入了解可以在我的博客搜索“Trie树”从一个节点连出去的边都必须标识不同的字符。所以一个节点最多有|字符集|这么多子节点。其中有一些节点是终结点,我们用黑色表示。对于每一个终结点,如果我们把从根到它的路径上的字符按顺序连起来,就对应着一个集合中的字符串比如上图中3号节点对应的路径0123上的字符串是inn,8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的
Trie树简介
Trie树,又称为前缀树或字符串树,我这里只是简单讲述一下Trie树,如果需要深入了解可以在我的博客搜索“Trie树”
首先看一下Trie树长什么样子
上面这棵 Trie 树包含的字符串集合是 {in, inn, int, tea, ten, to}每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串,字符集就是‘a’-‘z’;对于都是数字的字符串,字符集就是‘0’-‘9’;对于二进制字符串,字符集就是 0 和 1
从一个节点连出去的边都必须标识不同的字符。所以一个节点最多有|字符集|这么多子节点。其中有一些节点是终结点,我们用黑色表示。对于每一个终结点,如果我们把从根到它的路径上的字符按顺序连起来,就对应着一个集合中的字符串
比如上图中3号节点对应的路径0123上的字符串是inn,8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的
有穷自动机
上图有穷自动机中的 d
代表 0~9
的任一数字, E
代表科学计数法中的 e
, .
表示小数点,那么 7.3
、 .3
、 78
、 5e98
、 4e+3
、 1e-33
等都是该有穷自动机对应的文法,而 5.6e
、 78e+
等就不是该有穷自动机对应的文法
利用Trie树构建有穷自动机
就以上面的有穷自动机为例,构建Trie树我采用邻接矩阵的方法,具体来说就是用一个二维数组Trie[node][Charset]。解释一下这个二维数组,假设Trie[0]['d']=1,表达的意思就是0号结点能够通过字符'd'到达结点1;Trie[2]['d']=2的意思就是2号结点能通过字符'd'到达2号结点。根据这个规则,我们首先做出一个二维表
这个表的含义是通过起始结点经过什么字符能到达其他结点,如果为空说明从这个起始结点并不能到达该结点,那么根据这个表,我们就能构建出Trie树,因为数组的下标只能是数字,不能是字符,所以我们人为规定一下, d
代表0, .
代表1, e
代表2, +
或 -
代表3,举个例子,Trie[0][0]=1表示0号结点能通过数字到达1号结点;Trie[4][3]=5表示4号结点能通过 +
或 -
到达5号结点。我们首先把Trie树构建出来
trie[0][0] = 1; trie[0][1] = 3; trie[1][0] = 1; trie[1][1] = 2; trie[1][2] = 4; trie[2][0] = 2; trie[2][2] = 4; trie[3][0] = 2; trie[4][3] = 5; trie[4][0] = 6; trie[5][0] = 6; trie[6][0] = 6;
构建的Trie树如下图所示:
Trie树构建好了,我们应该知道怎么在Trie树中查找某个字符串是否存在,假设有这么一个字符串 3.14e3
,那么这棵树的结点转换过程就是 0->3->2->2->4->6
。
算法流程如下:
- 定义整型变量i,初始化为0,i的含义是指示当前取出的是字符串中的第i个字符
- 定义整型变量cur,初始化为0,表示当前处于几号结点
- 判断
Trie[cur][i]
的值是否存在,如果存在,则令cur = Trie[cur][i]
,如果不存在,这直接退出程序 - 重复执行3操作直到
i
等于字符串的长度 - 判断cur是否为终结状态,如果是,则打印成功;否则打印失败
代码
import java.util.*; public class Main { static Set<Integer> end = new HashSet<Integer>(); static Map<String, Integer> kv = new HashMap<String, Integer>(); static int[][] trie = new int[7][4]; // d = 0 // . = 1 // e = 2 // +|- = 3 static void init() {// 初始化Trie树 trie[0][0] = 1; trie[0][1] = 3; trie[1][0] = 1; trie[1][1] = 2; trie[1][2] = 4; trie[2][0] = 2; trie[2][2] = 4; trie[3][0] = 2; trie[4][3] = 5; trie[4][0] = 6; trie[5][0] = 6; trie[6][0] = 6; end.add(1); end.add(2); end.add(6); for (int i = 0; i <= 9; i++) kv.put(String.valueOf(i), 0); kv.put(".", 1); kv.put("e", 2); kv.put("+", 3); kv.put("-", 3); } static boolean check(String str) { int len = str.length(); int cur = 0; if (!Character.isDigit(str.charAt(len - 1)) && !".".equals("" + str.charAt(len - 1))) return false; for (int i = 0; i < len; i++) { String tmp = "" + str.charAt(i); int c = kv.get(tmp); if (trie[cur][c] == 0) // 等于0就表示不存在 return false; // 不存在就返回错误 cur = trie[cur][c]; // 存在就更新cur结点 } return end.contains(cur); // 判断最后是否到达终结状态 } public static void main(String[] args) { Scanner cin = new Scanner(System.in); String str = cin.next(); init(); if (check(str)) System.out.println("Right"); else System.out.println("Error"); cin.close(); } }
运行的GIF图如下:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 知多一点有限状态自动机
- 浅谈后缀自动机:概述,构建与简单应用
- goAcAutoMachine:Go 实现的 AC 自动机
- Python实现元胞自动机(康威生命游戏)
- 编译原理学习笔记-3:词法分析(一)基本过程、正规式和有限自动机
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
HTML 编码/解码
HTML 编码/解码
SHA 加密
SHA 加密工具