骨骼昂赛跪经

fisherhust 发表于 2018-1-9 05:02
你也加油! 过几个月再试试

嗯嗯, 我记得hr跟我说冷冻室9-12个月

第二题貌似是这个

https://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/

anywho 发表于 2018-2-2 11:46
第二题貌似是这个

https://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/

啊, 没错, 就是这个, 难度4.5, 挂了也认了

第二题可不可以做个前处理，把字典里每个单词的所有prefix 形式 reverse后存到 trie里，然后在stream时候每次来一个新字符就往前搜, 搜到一个reverse prefix 正好是一个完整的reverse word时就可以作为一个答案存起来，继续搜索直到无法继续或者设置一个max 搜索深度(单词长度不会过长，比如<=20字符)

补充内容 (2018-2-12 13:04):
其实都不用存prefix，建trie时直接存reverse word就好了。。。

codemonk 发表于 2018-2-12 10:30
第二题可不可以做个前处理，把字典里每个单词的所有prefix 形式 reverse后存到 trie里，然后在stream时候每 ...

感觉也可以吧, 怎么分析时间复杂度捏?

fisherhust 发表于 2018-2-12 12:01
感觉也可以吧, 怎么分析时间复杂度捏?

如果约束最大搜索深度为20， 那么每次搜索是 constant time。
建trie需要 O(l^2 * n), l 是单词长度，n是单词个数

补充内容 (2018-2-12 12:18):
老哥你怎么看？

codemonk 发表于 2018-2-12 12:17
如果约束最大搜索深度为20， 那么每次搜索是 constant time。
建trie需要 O(l^2 * n), l 是单词长度，n ...

老哥表示不太会啊, 等大牛来解释

你写了AC自动机？？？

hippopoint 发表于 2018-3-12 12:58
你写了AC自动机？？？

大概描述了一下, 好像没有仔细写

fisherhust 发表于 2018-3-12 22:47
大概描述了一下, 好像没有仔细写

太难了太难了，看来要强行背下来KMP后缀树AC自动机几大字符串神奇