利用Trie树构建有穷自动机

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。

算法流程如下：

1. 定义整型变量i，初始化为0，i的含义是指示当前取出的是字符串中的第i个字符
2. 定义整型变量cur，初始化为0，表示当前处于几号结点
3. 判断Trie[cur][i]的值是否存在，如果存在，则令cur = Trie[cur][i]，如果不存在，这直接退出程序
4. 重复执行3操作直到i等于字符串的长度
5. 判断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图如下：