[Revised] Trie上的动态规划：编辑距离与最长公共子序列的批量计算
给定一个称为文本的字符串，和一个词典，词典中的字符串称为模式。通过在Trie树上以DFS序执行动态规划算法，我们可以批量计算文本与每个模式的最长公共子序列长度与编辑距离。
DONG Yuxuan
DONG Yuxuan's Homepage
Latest posts
[Revised] The Implementation of Shsub: A Shell Template Engine Written in C
Shsub is a template engine of the Shell language, implemented in C. This paper explains the implementation of Shsub 2.0.1 to help potential contributors understand the code quickly.
The Implementation of Shsub: A Shell Template Engine Written in C
Shsub is a template engine of the shell language, implemented in C. This paper explains the implementation of Shsub 2.0.0 to help potential contributors understand the code quickly.
LNN: A Command-Line Program of Feedforward Neural Networks
LNN (Little Neural Network) is a command-line program training and running feedforward neural networks. LNN aims to make easy tasks easily done. This report contains a user’s guide and several examples to explain the design of LNN. This report describes the first version (0.0.1) of LNN. Like many programs, LNN evolves. There may be some new features of later versions not contained by this report.…
Storing a Trie with Compact and Predictable Space
This paper proposed a storing approach for trie structures, called coordinate hash trie. The basic idea is using a global hash table with a special hash function to store all edges of a trie. For a trie with n nodes and an alphabet with size m, the execution time of finding, inserting and deleting a child node, is O(1) for the average case, O(m) for the worst case. The space used by this approach…
Trie上的动态规划：编辑距离与最长公共子序列的批量计算
给定一个称为文本的字符串，和一个词典，词典中的字符串称为模式。 通过在Trie树上以DFS序执行动态规划算法， 我们可以批量计算文本与每个模式的最长公共子序列长度与编辑距离。