就是那个Ukknonen，看都没看懂，stackoverflow上那个高赞还是没看懂，求点拨。大佬们在实际工作中用到过这个吗？或者suffix array就行了
面试的话懂得 trie 就够了，实际工作中基本都是用 suffix array，因为省空间……
3 个赞
好几年了，一直对这个问题念念不忘
水老师专业户
1 个赞
可以啊水姐，不是盖的
1 个赞
所以楼主哪里不懂？
普通人的工作基本上用不到这个，就算你运气好用得到这个东西，大概率都已经被别人实现了，所以一般轮不到自己写。
2 个赞
竟然实用工作中也用suffix array 
1 个赞
suffix array好背 倍增简单 真正打竞赛一般也不会卡的（也可能科技进步了…
2 个赞
上面说的对的，后缀数组简单多了而且不比后缀树慢多少
1 个赞
读Gusfield p89-107。注意到：
Lemma: During the algorithm we never explicitly perform Rule 1 extensions.
Proof: Suppose we perform an explicit Rule 1 extension as the extension j of phase i. Clearly i > 1, j < i. Then in phase i-1, extension j is a Rule 3 extension, be it implicit or explicit. This means s[j…i-1] has appeared before in the string (i.e. as a substring of s with start index < j). But since extension j of phase i is a Rule 1 extension, s[j…i-1] is a path that leads to a leaf node after phase i-1, which means s[j…i-1] could not have appeared before. Contradiction.
Corollary: In each phase, all Rule 1 extensions are done implicitly, and we do some Rule 2 extensions explicitly until we do a Rule 3 extension explicitly, in which case we return early and proceed to the next phase.
于是有个非常简洁的实现。
2 个赞
谢谢～难以想象竟然是如此简单的代码。。。