识别一系列字符中的单词

Question

我需要一种能够识别没有空格的字符序列中的单词(基于字典)的算法.

比方说,例如,序列是:
无
空间它应该识别空间和更少.

并且可能存在可以识别更多单词的情况.很难给出这样的例子,但我会尝试一下:

例如:太空光
识别的单词:空格和轻微(1)
识别的单词:空格和光(2)

所以算法也应该能够找到那种变化.

Answer 1

如果您需要对同一字符串进行多个查询，后缀特里树是一个很好的解决方案。这将非常有效地存储字符串，并允许在 O(n) 中查找查询，其中 n 是查询的长度（请注意，除非您对查询有更多了解，否则您无法做得更好）。

如果后缀 trie 仍然占用太多空间，您可以使用 DAWG，但这构建起来要复杂得多。