模式匹配简介

作者：L. Grondin

问题

给定一个字符串集合，它们的字典树（通常发音为“try”以避免与一般术语树混淆）是一个根树，其形成方式如下。对于字符串中每个唯一的第一个符号，都会形成一条边，将根连接到一个新顶点。然后使用此符号标记边。

然后，我们可以通过向下移动一层来迭代该过程，如下所示。假设连接根节点到节点 *v* 的边用“A”标记；然后我们从集合中以“A”开头的每个字符串中删除第一个符号，然后将 *v* 视为我们的根节点。我们将此过程应用于与根节点相邻的所有节点，然后向下移动一层并继续。有关字典树的示例，请参见图 1。

作为这种构造方法的结果，从根节点到叶节点的字典树中任何路径的边上的符号将拼写出集合中的唯一字符串，只要集合中没有字符串是另一个字符串的前缀（这将导致第一个字符串被编码为终止于内部节点的路径）。

给定：最多 100 个 DNA 字符串的列表，每个字符串的长度最多为 100 bp，其中任何一个字符串都不是另一个字符串的前缀。

返回：对应于这些模式的字典树 *T* 的邻接表，格式如下。如果 *T* 有 *n* 个节点，首先用 1 标记根节点，然后按您喜欢的任何顺序用整数 2 到 *n* 标记其余节点。*T* 的邻接表中的每条边将由一个三元组编码，该三元组包含表示边的父节点的整数，后跟表示边的子节点的整数，最后是标记边的符号。

http://rosalind.info/problems/trie/

样本数据集

ATAGA
ATC
GAT

样本输出

1 2 A
2 3 T
3 4 A
4 5 G
5 6 A
3 7 C
1 8 G
8 9 A
9 10 T

用法

$ perl6 trie-grondilu.pl

或

$ perl6 trie-grondilu.pl --data="GAT ATC"

源代码：trie-grondilu.pl

use v6;

my Int $node = 1;

sub trie(@string is copy, $root = $node) {
    @string .= grep: *.chars;
    return {} if not @string;
    hash gather for @string.classify(*.substr: 0, 1).sort(*.key)>>.kv -> ($k, $v) {
        my @value = map *.substr(1), grep *.chars > 1, $v[];
        say "$root {++$node} $k";
        if (@value) {
            take $k => &?ROUTINE( @value, $node );
        }
    }
}

sub MAIN(:$data = "ATAGA ATC GAT") {
    my @input = $data.split(/\s+/);
    trie @input;
}