0

我了解ukkonen 的算法。我只是好奇如何将其扩展为包含多个字符串（以特殊字符“$”结尾）。

我在某处读到给定字符串 s1（比如“abcddefx$”）和 s2（比如“abddefgh$”），我应该通过 ukkonen 的算法正常插入 s1。然后用 s2 遍历树。那就是我应该在树中搜索 s2 。一旦我到达搜索结束的节点（“ab”，在“b”之后），我应该从那里恢复 ukkonen 算法。

我理解这背后的基本逻辑。但我很好奇的是，旧的后缀链接会发生什么。他们还有效吗？？？我也对我的三元组（active_node，active_length，remainder）感到困惑（节点代表“ab”，0,0），因为我开始新的通道？？？

4

1 回答 1

2

为了处理特殊字符，您可以使用Unicode Private Use Areas。这些是为您自己使用而保留的一些特殊字符范围，但是这些范围的大小只有大约 4000 个字符。根据您使用的语言的 unicode 支持，这可能非常容易或困难。

如果这不起作用，则不要将字符插入树中，而是将它们包装在某种其他类型的变量（结构、对象、字典）中以“扩展”它们的含义。这样您就可以提供所需的额外信息（这是字符串的结尾吗？这是哪个字符串的结尾？）。然后，您可以在这个新包装器上提供自定义运算符来实现相等，而不是直接使用字符。

于 2013-08-05T20:24:52.330 回答