谷歌店面.. 跪

是个没见过的题, 店面的天竺人不是特别友好. 随便介绍了一下自己就直接做题了.
google doc上写的, 题目是直接粘贴出来的, 没什么特别难理解的地方.
说给一个stream of characters, 例如 [a, a, a, a, a, ...]

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

找的window. 然后需要应该linkedlist来记录走过的character这样.
他也没多说什么, 最后代码也写得磕磕绊绊.

求大米!

Lz搜一下 ac自动机 ，初始化构建好后可以做到 O(1) 复杂度的判断是否match

用不着kmp把。就是倒序排trie，然后search就行。利口要领伞尔

这题我不太清楚是否需要后缀树（其实后缀树的具体意义我还没搞清。。）如果需要的话就有点蛋疼了。

我的想法是可以对词典内的所有单词翻转一下，然后建立前缀树，按照你说的保存一个最大window，然后新进来一个单词就用前缀树匹配。最后查一下能找到多少单词，这样复杂度会降低一点。

店面就问kmp..可以写一个简单状态机，最坏情况重复字符 o n^2

第一个想法是先建一个Trie，每次输入char时把把一个指向root的pointer 加到queue，再把所有queue里的指针往char方向挪一格，valid加回queue, invalid删掉，指到end of word就标记一下

我也觉得后缀树吧

huntersjm 发表于 2019/04/10 11:27:39
Lz搜一下 ac自动机 ，初始化构建好后可以做到 O(1) 复杂度的判断是否match

学习了，原来是trie +kmp

huntersjm 发表于 2019/04/10 11:27:39
Lz搜一下 ac自动机 ，初始化构建好后可以做到 O(1) 复杂度的判断是否match

这个，电面写得出来吗。。。

楼主面试以后多久收到消息的？

请问能重用字符流么? 比如流是abc, 字典是 ab, bc的话,怎么算?