字典树 (Trie) - OI Wiki

Ir1d commented 6 years ago

https://oi-wiki.org/string/trie/

thallium commented 5 years ago

在trie上的kmp就是ac自动机吗？

ShiinaMashiro19 commented 4 years ago

@thallium 在trie上的kmp就是ac自动机吗？

可以这么认为

Falicitas commented 4 years ago

题目fusion tree的第87 & 89行的if判定那写错了，应改为if(fa[fa[x]]!=-1)云云，由于rt周围的点若被修改会RE（虽然数据能过）

Enter-tainer commented 4 years ago

@Falicitas hello~可以帮忙开一个 pull request 修改一下吗

ShuYuMo2003 commented 4 years ago

@Falicitas 题目fusion tree的第87 & 89行的if判定那写错了，应改为if(fa[fa[x]]!=-1)云云，由于rt周围的点若被修改会RE（虽然数据能过）

我写的。。我改QAQ

ShuYuMo2003 commented 4 years ago

@Falicitas 题目fusion tree的第87 & 89行的if判定那写错了，应改为if(fa[fa[x]]!=-1)云云，由于rt周围的点若被修改会RE（虽然数据能过）

感谢！

Falicitas commented 4 years ago

@ShuYuMo2003 感谢！

233没事，大佬让蒟蒻学了一个神仙算法qwq（之前忘留意邮箱了233所以忘记pr了

izlyforever commented 3 years ago

请问 Fusion tree 可以写成变长的吗？非定长要考虑进位，然后进位之后 erase 就要变化了，然后把我人变傻了，好气啊！（终于 debug 好了，交了20多次，人交傻了）

ShuYuMo2003 commented 3 years ago

@izlyforever 请问 Fusion tree 可以写成变长的吗？非定长要考虑进位，然后进位之后 erase 就要变化了，然后把我人变傻了，好气啊！（终于 debug 好了，交了20多次，人交傻了）

我尝试过的。

基本就是人没了… 没法调试… 情况比较多

如果说变成的trie可以做到更小的内存消耗，随机数据也许可以，但是构造数据也是能卡满的，空间复杂度是 $\mathcal{O}(n \log n)$ 的，应该不算很劣吧。

dingzhuoustb commented 3 years ago

1000(10) + 1 = 1001(11) ; 全局加1，第一个例子，应该是1000(8) + 1 = 1001(9)

StLeoX commented 2 years ago

所以这个AC Automaton与Lexer里面的DFA有什么联系？

CoelacanthusHex commented 2 years ago

@StLeoX Informally, the AC algorithm constructs a finite-state automaton that resembles a trie with additional links between the various internal nodes. And, DFA is deterministic finite-state automaton.

OI-wiki / gitment

字典树 (Trie) - OI Wiki #107