c - 如何在 C 中实现紧凑有向无环字图 (CDAWG)？

Question

如何在 C 中实现这种数据结构？它是一种类似于 DAWG 的结构，但空间效率是 DAWG 的两倍，比仅压缩前缀的 trie 更有效。

Answer 1

从我可以从这篇论文中看到

这是一个带有后缀压缩的 trie，以减少比赛的最终状态变化，因为我做过类似的事情，我也考虑过这样做以节省空间。这是我为数据结构想到的解决方案，我很想看看是否还有其他方法：

struct cdawg
{
    int issuffix:1;
    int length:31;
    char *s; // suffix if issuffix == 1, else array of valid transition chars
    struct cdawg *trans; // array of next states based on the index of trans char in s, null if suffix
};